Overview

This problem asks us to quickly find the coordinates of a boat moving according to certain rules in a river with changing flow velocities at multiple specified times \(X_j\).

Simulating the movement naively for each query will not run within the time limit. Therefore, we can answer each query quickly by combining precomputation using cumulative sums and binary search.

Analysis

1. Determining the Boat’s Velocity

The velocity of the boat changes depending on the direction of the river flow. Let \(S_i\) be the velocity of the boat (relative to the ground) in the time interval from \(T_i\) to \(T_{i+1}\). It can be expressed as follows:

• When the river flows east (\(W_i > 0\)): $\(S_i = W_i + V\)$
• When the river flows west (\(W_i < 0\)): $\(S_i = W_i - V\)$

Note that there is no river flow during the time interval from \(0\) to less than \(T_1\), so the boat does not move (velocity is \(0\), coordinate is \(0\)).

2. Naive Approach and Its Limitations

For each query (at time \(X\)), if we calculate the coordinate by sequentially adding up “how much time was spent in which interval” starting from time \(0\), it takes \(O(N)\) time per query. Since the maximum number of queries is \(Q = 10^5\) and the number of changes in river flow is \(N = 10^5\), the overall time complexity would be \(O(NQ) \approx 10^{10}\), which will significantly exceed the time limit (usually 2.0 seconds) and result in a Time Limit Exceeded (TLE).

3. Optimization Ideas

To answer queries quickly, we employ the following two techniques:

1. Precomputing coordinates at the transition points (Cumulative Sums) Let \(P_i\) be the coordinate of the boat at each transition time \(T_i\) when the river flow changes. The coordinate at time \(T_1\) is \(P_1 = 0\). Subsequent coordinates can be sequentially calculated by adding the coordinate at the previous transition point and the distance traveled in that interval as follows: $\(P_i = P_{i-1} + S_{i-1} \times (T_i - T_{i-1}) \quad (2 \leq i \leq N)\)\( We precompute this in \)O(N)$ time.

2. Identifying the interval using Binary Search We need to identify which time interval the given time \(X\) belongs to, i.e., find \(i\) such that \(T_i \leq X < T_{i+1}\). Since the time array \(T\) is monotonically increasing (\(T_1 < T_2 < \cdots < T_N\), i.e., sorted), we can find this \(i\) in \(O(\log N)\) time using binary search (such as std::upper_bound in C++).

By using these, the coordinate at time \(X\) can be calculated in constant time \(O(1)\) as follows: - When \(X < T_1\): the coordinate is \(0\) - When there exists a maximum \(i\) such that \(T_i \leq X\): the coordinate is \(P_i + S_i \times (X - T_i)\)

Algorithm

1. Input Reception and Velocity Calculation Calculate the boat’s velocity \(S_i\) in each interval.
2. Precomputing Coordinates at Transition Points Calculate the coordinates \(P_i\) at each transition time \(T_i\) sequentially from \(i = 2\) to \(N\) in a cumulative sum fashion.
3. Answering Queries For each query \(X\):
   • Use binary search (std::upper_bound) to find the maximum index \(i\) such that \(T_i \leq X\).
   • If \(i\) does not exist (\(X < T_1\)), the answer is \(0\).
   • If it exists, the answer is \(P_i + S_i \times (X - T_i)\).

Complexity

• Time Complexity: \(O(N + Q \log N)\)

  • Precomputation (calculating the velocities and coordinates at each transition point) takes \(O(N)\) time.
  • For each query, binary search takes \(O(\log N)\) time. Since this is performed \(Q\) times, the total query processing time is \(O(Q \log N)\).
  • Since \(N, Q \leq 10^5\), the total number of operations is approximately \(2 \times 10^6\), which easily runs within the time limit.

• Space Complexity: \(O(N)\)

  • The sizes of the arrays storing the times \(T\), river flow velocities \(W\), boat velocities \(S\), and coordinates at transition points \(P\) are all \(O(N)\).

Key Implementation Points

• Avoiding Overflow In the calculation process, the coordinate values can reach up to approximately \(2 \times 10^{18}\). Although this fits within the maximum value of a standard 64-bit signed integer type (long long, which is about \(9 \times 10^{18}\)), to eliminate the risk of temporary overflow during multiplication, the provided code uses a 128-bit integer type (__int128_t).

• Fast I/O Since \(N\) and \(Q\) are large, in C++, we speed up the input and output by untying std::cin and std::cout (disabling synchronization with stdio).

  Source Code

#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;
}

---

This editorial was generated by gemini-3.5-flash-high.