Overview

While the river’s flow velocity changes at times \(T_1, T_2, \ldots, T_N\), Takahashi’s velocity relative to the ground while rowing the boat remains constant within each interval. This problem asks us to find Takahashi’s coordinates at multiple given times \(X_j\).

Analysis

For each query time \(X\), simulating the movement from time \(0\) to \(X\) naively would take \(O(N)\) time per query, resulting in a total time complexity of \(O(NQ)\) and a TLE (Time Limit Exceeded) verdict. Since both \(N\) and \(Q\) are at most \(10^5\), we need a faster approach.

To organize the problem, the boat’s movement is divided into the following \(N\) time intervals: - From time \(0\) to less than \(T_1\): velocity \(0\) - From time \(T_1\) to less than \(T_2\): velocity \(v_1\) - \(\ldots\) - From time \(T_i\) to less than \(T_{i+1}\): velocity \(v_i\)

Since the velocity is constant within each interval, if we precompute Takahashi’s coordinate \(P_i\) at each time \(T_i\), we can find the coordinate at any time \(X\) in \(O(1)\) time as \(P_{idx-1} + (X - T_{idx-1}) \times v_{idx-1}\) by identifying the interval \([T_{idx-1}, T_{idx})\) containing \(X\).

We can quickly find which interval \(X\) belongs to by using binary search.

Algorithm

1. Velocity Calculation: Calculate the velocity relative to the ground \(v_i\) for each time interval. If the flow is eastward (\(W_i > 0\)), it is \(W_i + V\); if westward (\(W_i < 0\)), it is \(W_i - V\).
2. Prefix Sum Calculation: Compute the coordinate \(P_i\) at each transition time \(T_i\). Set \(P_0 = 0\) and calculate cumulatively as \(P_i = P_{i-1} + (T_i - T_{i-1}) \times v_{i-1}\) (for convenience, let \(T_0 = 0\)).
3. Binary Search: For each query \(X\), use binary search (such as upper_bound) to find which interval \(X\) belongs to.
   • If \(X < T_1\), the coordinate is \(0\).
   • Otherwise, assuming \(X\) falls in the interval from \(T_{idx-1}\) to less than \(T_{idx}\) (or after \(T_N\)), calculate the coordinate as \(P_{idx-1} + (X - T_{idx-1}) \times v_{idx-1}\).

Complexity

• Time Complexity: \(O(N + Q \log N)\) in total, as precomputation takes \(O(N)\) and each query takes \(O(\log N)\) for binary search.
• Space Complexity: \(O(N)\) to store times, velocities, and coordinates at each time.

Implementation Points

• Since the travel distance and coordinates can become extremely large (on the order of \(10^9\) for \(X\) and \(V\)), you must use 64-bit integers (long long in C++) to prevent overflow.

• When using binary search to find the interval containing \(X\), ensure that the start of the interval is correctly matched with its corresponding velocity.

  Source Code

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

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

    vector<long long> P(N);
    // P[i] is the coordinate at time T[i]
    if (N > 0) {
        P[0] = 0;
        for (int i = 1; i < N; ++i) {
            P[i] = P[i - 1] + (T[i] - T[i - 1]) * v[i - 1];
        }
    }

    for (int j = 0; j < Q; ++j) {
        long long X;
        cin >> X;
        int idx = upper_bound(T.begin(), T.end(), X) - T.begin();
        long long ans;
        if (idx == 0) {
            ans = 0;
        } else if (idx == N) {
            ans = P[N - 1] + (X - T[N - 1]) * v[N - 1];
        } else {
            ans = P[idx - 1] + (X - T[idx - 1]) * v[idx - 1];
        }
        cout << ans << "\n";
    }

    return 0;
}

This editorial was generated by or-glm5.2-high.