概要

川の流れが変化するたびに、ボートの地面に対する速度も変化します。
各時間帯では速度が一定なので、あらかじめ各変化時刻での座標を計算しておき、各質問には二分探索で答えます。

考察

川の流れの速度が \(W\) のとき、高橋君は流れと同じ方向に水面に対して速さ \(V\) で漕ぎます。

したがって、地面に対するボートの速度は次のようになります。

• \(W > 0\) のとき、東向きに流れているので速度は \(W + V\)
• \(W < 0\) のとき、西向きに流れているので速度は \(W - V\)

つまり、各流れの変化後の速度を

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

として考えればよいです。

時刻 \(0\) から \(T_1\) までは川の流れがないため、座標はずっと \(0\) です。
その後は、各区間で速度が一定なので、座標は直線的に変化します。

例えば、時刻 \(T_i\) での座標が分かっていれば、同じ区間内の時刻 \(X\) における座標は

\[ \text{座標} = \text{pos}_i + \text{vel}_i \times (X - T_i) \]

で求められます。

素朴に各質問ごとに最初から流れの変化を順に追うと、最悪で \(O(NQ)\) かかります。
\(N + Q \leq 2 \times 10^5\) なので、これは間に合いません。

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

アルゴリズム

まず、各区間での地面に対する速度を計算します。

コードでは \(0\)-indexed で扱っているため、\(T[i]\) は問題文の \(T_{i+1}\) に対応します。

vel[i] = W[i] + (W[i] > 0 ? V : -V);

次に、各変化時刻での座標を pos に保存します。

• pos[i] : 時刻 T[i] における高橋君の座標

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

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

です。

その後は、前の変化時刻から現在の変化時刻まで一定速度で進むので、

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

で計算できます。

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

1. もし \(X < T_1\) なら、まだ川の流れがないので答えは \(0\)
2. そうでなければ、\(T_i \leq X\) となる最大の \(i\) を二分探索で求める
3. その区間内では速度 vel[i] が一定なので、

\[ \text{答え} = \text{pos}[i] + \text{vel}[i] \times (X - T[i]) \]

を出力します。

二分探索には upper_bound を使います。

int idx = int(upper_bound(T.begin(), T.end(), X) - T.begin()) - 1;

これは「\(X\) 以下である最後の \(T_i\) の位置」を求めています。

計算量

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

実装のポイント

座標や速度、時間の積は大きくなる可能性があります。

例えば、速度は最大でおよそ \(2 \times 10^9\)、時間差は最大で \(10^9\) なので、積は \(2 \times 10^{18}\) 程度になることがあります。
そのため、int ではなく long long を使う必要があります。

また、時刻 \(T_N\) 以降も最後の速度 vel[N-1] で進み続けるため、upper_bound による二分探索はそのまま使えます。

ソースコード

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    long long V;
    cin >> N >> V >> Q;

    vector<long long> T(N), W(N), vel(N);
    for (int i = 0; i < N; i++) {
        cin >> T[i] >> W[i];
        vel[i] = W[i] + (W[i] > 0 ? V : -V);
    }

    vector<long long> pos(N, 0);
    for (int i = 1; i < N; i++) {
        pos[i] = pos[i - 1] + vel[i - 1] * (T[i] - T[i - 1]);
    }

    while (Q--) {
        long long X;
        cin >> X;

        if (X < T[0]) {
            cout << 0 << '\n';
            continue;
        }

        int idx = int(upper_bound(T.begin(), T.end(), X) - T.begin()) - 1;
        long long ans = pos[idx] + vel[idx] * (X - T[idx]);
        cout << ans << '\n';
    }

    return 0;
}

---

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