概要

川の流れの速度は区間ごとに一定なので、高橋君の速度も区間ごとに一定です。
各変化時刻での座標を前計算しておき、各質問時刻がどの区間に属するかを二分探索で求めます。

考察

時刻 \(T_i\) 以降、次の変化時刻までは川の流れの速度が一定です。

川の流れの速度を \(W_i\) とすると、高橋君の地面に対する速度は次のようになります。

• \(W_i > 0\) のとき、東向きに \(W_i + V\)
• \(W_i < 0\) のとき、西向きに \(|W_i| + V\)、つまり速度は \(W_i - V\)

したがって、各区間での速度は一定です。

例えば、区間 \([T_i, T_{i+1})\) における速度を \(u_i\) とすると、

\[ u_i = \begin{cases} W_i + V & (W_i > 0) \\ W_i - V & (W_i < 0) \end{cases} \]

です。

時刻 \(0\) から \(T_1\) までは川の流れがないため、高橋君は動きません。
よって、時刻 \(T_1\) における座標は \(0\) です。

素朴に各質問について最初から区間を順にたどると、\(1\) クエリあたり \(O(N)\) かかります。
\(N, Q\) は合わせて最大 \(2 \times 10^5\) なので、最悪で \(O(NQ)\) となり間に合いません。

そこで、あらかじめ各変化時刻 \(T_i\) における座標を前計算しておきます。
そして、質問時刻 \(X_j\) がどの区間に属するかを二分探索で求めれば、各質問を \(O(\log N)\) で処理できます。

アルゴリズム

まず、各区間での速度を計算します。

\[ \text{vel}[i] = \begin{cases} W_i + V & (W_i > 0) \\ W_i - V & (W_i < 0) \end{cases} \]

これは、時刻 \(T_i\) 以降の区間での高橋君の速度です。

次に、配列 \(\text{pos}\) を用意します。
\(\text{pos}[i]\) を「時刻 \(T_i\) における座標」とします。

時刻 \(T_1\) までは動かないので、

\[ \text{pos}[0] = 0 \]

です。

その後は、前の変化時刻から現在の変化時刻までの移動量を足していきます。

\[ \text{pos}[i] = \text{pos}[i-1] + (T_i - T_{i-1}) \times \text{vel}[i-1] \]

これで、すべての変化時刻における座標が求まります。

各質問時刻 \(X\) に対しては、以下のように答えます。

1. \(T_i \leq X\) を満たす最大の \(i\) を二分探索で求める
2. そのような \(i\) が存在しない、つまり \(X < T_1\) なら答えは \(0\)
3. そうでなければ、時刻 \(T_i\) から \(X\) まで速度 \(\text{vel}[i]\) で進むので、

\[ \text{answer} = \text{pos}[i] + (X - T_i) \times \text{vel}[i] \]

となります。

Python では、bisect_right(T, x) - 1 によって「\(x\) 以下である最大の \(T_i\) の添字」を求めています。

計算量

• 時間計算量: \(O(N + Q \log N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 時刻 \(X\) がちょうど \(T_i\) と等しい場合、その時刻から新しい速度 \(W_i\) が適用されます。
  そのため、二分探索には bisect_right を使い、\(T_i \leq X\) となる最大の添字を取得します。

• \(X < T_1\) の場合は、川の流れがなく高橋君は動かないので、答えは必ず \(0\) です。

• 座標や移動量は大きくなる可能性があるため、Python 以外の言語では 64 bit 整数型を使う必要があります。

  ソースコード

import sys
from bisect import bisect_right

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    N = next(it)
    V = next(it)
    Q = next(it)

    T = [0] * N
    vel = [0] * N

    for i in range(N):
        t = next(it)
        w = next(it)
        T[i] = t
        vel[i] = w + V if w > 0 else w - V

    pos = [0] * N
    for i in range(1, N):
        pos[i] = pos[i - 1] + (T[i] - T[i - 1]) * vel[i - 1]

    ans = []
    for _ in range(Q):
        x = next(it)
        idx = bisect_right(T, x) - 1
        if idx < 0:
            ans.append("0")
        else:
            ans.append(str(pos[idx] + (x - T[idx]) * vel[idx]))

    sys.stdout.write("\n".join(ans))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.5-high によって生成されました。