[AOJ] No. 0622 JOI国のお散歩事情 (Walking in JOI Kingdom)

2019年8月24日2019年11月3日

問題

方針

両者が散歩の途中で出会う座標

両者が散歩をしているときに出会う座標を求めます。これは、既に立ち止まっている国民に出会う点ではないことに注意して考えます。どのようなときに、両者が散歩をしているときに出会うかといいうと、東側に進む国民の座標を \( r \)、西側に進む国民の座標を \( l \) とすると、\( r < l  \wedge l – r \leq 2T\) のとき、

\[ \dfrac{r + l}{2} \]

の座標で出会うことになります。

次に、両者が散歩の途中で出会う座標のリスト \( p \) を作ります。全体の国民が一斉に動くので、西側から東側に向かって走査することを考えます。まず初めに、\( r = 0, l = 0 \) と初期化します。次に、走査していくなかで、\( r, l \) の値を更新し、それらの値が \( r \neq 0 \wedge l  \neq 0 \) のとき、 上記の条件を満たすならば、\( r, l \) を元にリストに座標を追加します。

\( T \) 秒後の全国民の位置

東側に向かって進む国民

東側に向かって進む国民について考えます。\( p \) の添え字を \( j \) とし、初期値は \( j = 0 \) とします。東側に向かって進む国民 \( i \) について、\( p_j < A_i \) を満たすとき、\( j \) の値をインクリメントします。\( j \) が \( p \) の末尾を超えるとき、その国民は \( A_i + T \) の位置に留まることになります。\( p_j \geq A_i \) を満たすとき、\( A_i \leq p_j \leq A_i + T \) を満たすならば、\( p_j \) に留まることになり、そうではないとき、 \( A_i + T \) の位置に留まることになります。そして、\( i + 1 \) 以降の東側に向かって進む国民について同様について走査します。

西側に向かって進む国民

東側に向かって進む国民のときと同様の考えで、西側から東側に向かって、西側に進む国民について走査します。注意する点として、\( p \) の末尾から先頭に向かって探索を行うことが挙げられます。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Data {
  int X, id;
  ll A;
  Data(int id, int X, ll A) : id(id), X(X), A(A){}
};

int main() {
  int N, Q;
  ll T;
  cin >> N >> T >> Q;
  ll A[N];
  int D[N];
  int X[Q];
  for (int i = 0; i < N; i++) {
    cin >> A[i] >> D[i];
  }
  for (int i = 0; i < Q; i++) {
    cin >> X[i];
    X[i]--;
  }
  ll r = 0;
  ll l = 0;
  vector<ll> p;
  vector<Data> dr;
  vector<Data> dl;
  for (int i = 0; i < Q; i++) {
    if (D[X[i]] == 1) {
      dr.push_back(Data(i, X[i], A[X[i]]));
    } else {
      dl.push_back(Data(i, X[i], A[X[i]]));
    }
  }

  for (int i = 0; i < N; i++) {
    if (D[i] == 1) {
      r = A[i];
    } else {
      l = A[i];
    }
    if (r == 0 || l == 0) continue;
    if (abs(l - r) <= 2 * T && r < l) {
      p.push_back((l + r) / 2);
      l = 0;
      r = 0;
    }
  }
  
  int ir = 0;
  ll t[Q];
  for (int i = 0; i < dr.size(); i++) {
    int X = dr[i].X;
    t[dr[i].id] = A[X] + T;
    while (ir < p.size()) {
      if (p[ir] < A[X]) {
        ir++;
      } else if (A[X] <= p[ir] && p[ir] <= t[dr[i].id]) {
        t[dr[i].id] = p[ir];
        break;
      } else {
        break;
      }
    }
  }
 
  int il = p.size() - 1;
  for (int i = dl.size() - 1; i >= 0; i--) {
    int X = dl[i].X;
    t[dl[i].id] = A[X] - T;
    while (il >= 0) {
      if (A[X] < p[il]) {
        il--;
      } else if (t[dl[i].id] <= p[il] && p[il] <= A[X]) {
        t[dl[i].id] = p[il];
        break;
      } else {
        break;
      }
    }
  }

  for (ll i : t) {
    cout << i << "\n";
  }
  return 0;
}