概要

この問題は、流速が変化する川において、ルールに従って移動するボートの、指定された複数の時刻 \(X_j\) における座標を高速に求める問題です。

各クエリに対して愚直にシミュレーションを行うと実行時間制限に間に合わないため、累積和を用いた前計算と二分探索を組み合わせることで、各クエリに高速に答えます。

考察

1. ボートの速度の整理

ボートの速度は、川の流れの向きによって以下のように変化します。時刻 \(T_i\) から \(T_{i+1}\) までの区間におけるボートの（地面に対する）速度を \(S_i\) とすると、次のように表せます。

• 川の流れが東向き（\(W_i > 0\)）のとき： $\(S_i = W_i + V\)$
• 川の流れが西向き（\(W_i < 0\)）のとき： $\(S_i = W_i - V\)$

なお、時刻 \(0\) 以上 \(T_1\) 未満の間は川の流れがないため、ボートは動きません（速度 \(0\)、座標 \(0\)）。

2. 素朴なアプローチとその限界

各クエリ（時刻 \(X\)）に対して、時刻 \(0\) から順に「どの区間にどれだけの時間滞在したか」を足し合わせて座標を計算すると、1つのクエリあたり \(O(N)\) の計算量がかかります。 クエリの数は最大で \(Q = 10^5\)、川の流れの変化回数は \(N = 10^5\) であるため、全体の計算量は \(O(NQ) \approx 10^{10}\) となり、実行時間制限（通常 2.0 秒）を大幅に超過してしまいます (TLE)。

3. 高速化のアイデア

クエリに高速に答えるために、以下の2つの工夫を行います。

1. 変化点での座標の前計算（累積和） 川の流れが変化する各時刻 \(T_i\) におけるボートの座標を \(P_i\) とします。 時刻 \(T_1\) における座標は \(P_1 = 0\) です。それ以降の座標は、1つ前の変化点での座標と、その区間での移動距離を足すことで、以下のように順次求めることができます。 $\(P_i = P_{i-1} + S_{i-1} \times (T_i - T_{i-1}) \quad (2 \leq i \leq N)\)\( これをあらかじめ \)O(N)$ で計算しておきます。

2. 二分探索による区間の特定 与えられた時刻 \(X\) がどの時間帯に属するか、すなわち \(T_i \leq X < T_{i+1}\) を満たす \(i\) を特定する必要があります。 時刻の配列 \(T\) は \(T_1 < T_2 < \cdots < T_N\) と単調増加（ソートされた状態）であるため、二分探索（C++の std::upper_bound）を使うことで、この \(i\) を \(O(\log N)\) で見つけることができます。

これらを用いることで、時刻 \(X\) における座標は以下の定数時間 \(O(1)\) で計算可能になります。 - \(X < T_1\) のとき：座標は \(0\) - \(T_i \leq X\) となる最大の \(i\) が存在するとき：座標は \(P_i + S_i \times (X - T_i)\)

アルゴリズム

1. 入力の受け取りと速度の計算 各区間におけるボートの速度 \(S_i\) を計算します。
2. 変化点における座標の前計算 各変化時刻 \(T_i\) における座標 \(P_i\) を、累積和の要領で \(i = 2\) から \(N\) まで順に計算します。
3. クエリへの回答 各クエリ \(X\) に対し：
   • 二分探索（std::upper_bound）を用いて、\(T_i \leq X\) となる最大のインデックス \(i\) を求めます。
   • \(i\) が存在しない（\(X < T_1\)）なら、答えは \(0\) です。
   • 存在するなら、答えは \(P_i + S_i \times (X - T_i)\) です。

計算量

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

  • 前計算（速度と各変化点での座標の計算）に \(O(N)\) かかります。
  • 各クエリに対し、二分探索に \(O(\log N)\) かかります。これが \(Q\) 回行われるため、クエリ処理全体で \(O(Q \log N)\) となります。
  • \(N, Q \leq 10^5\) であるため、全体の計算回数は約 \(2 \times 10^6\) 回となり、制限時間内に余裕で間に合います。

• 空間計算量: \(O(N)\)

  • 時刻 \(T\)、流速 \(W\)、ボートの速度 \(S\)、変化点での座標 \(P\) を格納する配列のサイズはすべて \(O(N)\) です。

実装のポイント

• オーバーフローの回避 計算の過程で座標の値は最大で \(2 \times 10^{18}\) 程度に達します。これは通常の 64 bit 整数型（long long）の最大値（約 \(9 \times 10^{18}\)）に収まりますが、掛け算の過程などで一時的にオーバーフローする危険を排除するため、提示されたコードでは 128 bit 整数型（__int128_t）を使用しています。

• 高速な入出力 \(N, Q\) が大きいため、C++では std::cin と std::cout の同期を切ることで入出力を高速化しています。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

typedef __int128_t int128;

// Helper function to print __int128_t values
void print128(int128 x) {
    if (x < 0) {
        cout << '-';
        x = -x;
    }
    if (x == 0) {
        cout << 0;
        return;
    }
    string s;
    while (x > 0) {
        s += (char)('0' + (x % 10));
        x /= 10;
    }
    reverse(s.begin(), s.end());
    cout << s;
}

int main() {
    // Optimize standard I/O operations for performance
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long V;
    int Q;
    if (!(cin >> N >> V >> Q)) return 0;

    vector<long long> T(N + 1);
    vector<long long> W(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> T[i] >> W[i];
    }

    // S[i] is the velocity of the boat in the interval starting from T_i
    vector<int128> S(N + 1);
    for (int i = 1; i <= N; ++i) {
        if (W[i] > 0) {
            S[i] = W[i] + V;
        } else {
            S[i] = W[i] - V;
        }
    }

    // P[i] is the position of the boat at time T_i
    vector<int128> P(N + 1);
    P[1] = 0;
    for (int i = 2; i <= N; ++i) {
        P[i] = P[i - 1] + S[i - 1] * (T[i] - T[i - 1]);
    }

    // Process queries
    for (int q = 0; q < Q; ++q) {
        long long X;
        cin >> X;
        
        // Find the largest i such that T_i <= X
        auto it = upper_bound(T.begin() + 1, T.end(), X);
        int idx = distance(T.begin(), it) - 1;
        
        if (idx == 0) {
            cout << 0 << "\n";
        } else {
            int128 ans = P[idx] + S[idx] * (X - T[idx]);
            print128(ans);
            cout << "\n";
        }
    }

    return 0;
}

---

この解説は gemini-3.5-flash-high によって生成されました。