Overview

This problem asks us to find the total number of times Takahashi and Aoki overtake each other as they run along a straight course at different constant speeds, stopping at water stations for different durations. By calculating the arrival and departure times at each water station and determining when their relative order changes in each interval and at each water station, we can compute the total number of overtakes in \(O(N)\) time.

Analysis

1. Eliminating Decimals (Time Scale Transformation)

Takahashi’s speed is \(V\) and Aoki’s speed is \(W\). The time required to travel a distance of \(1\) is \(\frac{1}{V}\) seconds for Takahashi and \(\frac{1}{W}\) seconds for Aoki. Calculating with these values directly would cause precision issues due to floating-point numbers.

To avoid this, we multiply all time units by \(V \times W\). This allows us to represent all times as integers. - Time taken to travel a distance of \(1\): \(W\) for Takahashi, \(V\) for Aoki. - Stopping time at water station \(i\): \(R_i \times V \times W\) for Takahashi, \(S_i \times V \times W\) for Aoki.

Note: Since \(V, W, R_i \le 10^9\), the result of the multiplications can reach up to approximately \(10^{27}\). This will overflow a standard 64-bit integer (long long), so we need to use C++’s 128-bit integer type (__int128_t).

2. Classification of Overtaking Locations

The moments when an overtake occurs can be broadly classified into the following two cases:

Case A: While moving from water station \(i-1\) to water station \(i\) (open interval \((i-1, i)\))

While moving, both run at their respective constant speeds. Thus, at most \(1\) overtake can occur within this interval. If their relative order immediately after departing water station \(i-1\) is different from their relative order immediately before arriving at water station \(i\), then exactly \(1\) overtake occurs during the movement.

Case B: While staying at water station \(i\) (at water station \(i\))

This is the case where one person is resting at the water station while the other catches up and overtakes them. For this to happen, both of the following conditions must be met: 1. Overlap in stay durations: There is some period of time where both are at water station \(i\) simultaneously. 2. Reversal of relative order: Their relative order when arriving at water station \(i\) is different from their relative order when departing water station \(i\).

---

Algorithm

Step 1: Calculating Arrival and Departure Times

Let Takahashi’s arrival time at water station \(i\) be \(a_i\) and his departure time be \(a'_i\). Similarly, let Aoki’s arrival and departure times be \(b_i\) and \(b'_i\) respectively. These can be calculated sequentially from \(i = 1\) to \(N\) using the following recurrence relations (with initial values \(a_0 = a'_0 = b_0 = b'_0 = 0\)):

• Takahashi:
  • \(a_i = a'_{i-1} + W\)
  • \(a'_i = a_i + R_i \times V \times W\) (except at the goal \(i=N\), where \(a'_N = a_N\))
• Aoki:
  • \(b_i = b'_{i-1} + V\)
  • \(b'_i = b_i + S_i \times V \times W\) (except at the goal \(i=N\), where \(b'_N = b_N\))

Step 2: Tracking Relative Order and Detecting Overtakes

We introduce a variable current_sign to represent the current relative order (\(+1\) if Takahashi is ahead, \(-1\) if Aoki is ahead). Immediately after the start, the faster runner will pull ahead, so we initialize it to \(+1\) if \(V > W\), and \(-1\) otherwise.

For each \(i = 1, 2, \ldots, N\), we perform the following checks:

1. Overtake Detection While Moving

Compare their relative order immediately after departing water station \(i-1\) (the sign of the departure time difference \(b'_{i-1} - a'_{i-1}\)) with their relative order upon arriving at water station \(i\) (the sign of the arrival time difference \(b_i - a_i\)). If these two signs are different, we determine that an overtake occurred while moving, increment the answer by \(1\), and flip the sign of current_sign.

2. Overtake Detection at Water Station \(i\) (only for \(i < N\))

We define the relative order upon arriving at water station \(i\) as \(S_{in}\), and upon departing as \(S_{out}\). - At arrival \(S_{in}\): - The one who arrives earlier (smaller arrival time) is ahead. If they arrive at the same time, they maintain the previous relative order, current_sign. - At departure \(S_{out}\): - The one who departs earlier (smaller departure time) is ahead. If they depart at the same time, the faster runner will pull ahead immediately after departing, so Takahashi is ahead (\(+1\)) if \(V > W\), and Aoki is ahead (\(-1\)) otherwise.

If their stay intervals at water station \(i\), \([a_i, a'_i]\) and \([b_i, b'_i]\), overlap (condition: \(a_i \le b'_i\) and \(b_i \le a'_i\)), and \(S_{in} \neq S_{out}\), we determine that an overtake occurred at the water station and increment the answer by \(1\). After that, we update current_sign to \(S_{out}\) and proceed to the next step.

---

Complexity

• Time Complexity: \(O(N)\)
  • We only run a single loop from \(1\) to \(N\), and the processing inside each loop consists entirely of \(O(1)\) arithmetic operations. Thus, the overall time complexity is \(O(N)\).
• Space Complexity: \(O(N)\)
  • Since we store several arrays of size \(N+1\) to record the arrival and departure times at each water station, the space complexity is \(O(N)\).

---

Implementation Details

• Using 128-bit Integers: We use C++’s __int128_t to prevent overflow when converting the time scale. Since __int128_t cannot be directly read or written using standard std::cin or std::cout, we read the input as long long and cast it to __int128_t during the calculation.

• Handling the Goal Exception: As specified in the problem statement, they do not stop to rest at the goal (water station \(N\)), which is equivalent to \(R_N = S_N = 0\). Furthermore, any overtake occurring at the exact moment they reach the goal is not counted, so we adjust the loop conditions to avoid performing the overtake detection during the stay at water station \(N\).

  Source Code

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

using namespace std;

using int128 = __int128_t;

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

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

    vector<long long> R(N + 1), S(N + 1);
    for (int i = 1; i <= N; ++i) cin >> R[i];
    for (int i = 1; i <= N; ++i) cin >> S[i];

    // a[i] and b[i] store the arrival times at station i (scaled by V * W)
    // a_prime[i] and b_prime[i] store the departure times from station i (scaled by V * W)
    vector<int128> a(N + 1), a_prime(N + 1);
    vector<int128> b(N + 1), b_prime(N + 1);

    a[0] = 0; a_prime[0] = 0;
    b[0] = 0; b_prime[0] = 0;

    int128 VW = (int128)V * W;

    for (int i = 1; i <= N; ++i) {
        a[i] = a_prime[i-1] + W;
        if (i < N) {
            a_prime[i] = a[i] + (int128)R[i] * VW;
        } else {
            a_prime[i] = a[i]; // No stopping at the goal
        }

        b[i] = b_prime[i-1] + V;
        if (i < N) {
            b_prime[i] = b[i] + (int128)S[i] * VW;
        } else {
            b_prime[i] = b[i]; // No stopping at the goal
        }
    }

    long long ans = 0;
    // current_sign: +1 if Takahashi is ahead, -1 if Aoki is ahead
    int current_sign = (V > W) ? 1 : -1;

    for (int i = 1; i <= N; ++i) {
        // 1. Check for overtaking inside the open interval (i-1, i)
        int128 R_prev = b_prime[i-1] - a_prime[i-1];
        int128 L_curr = b[i] - a[i];
        if ((R_prev > 0 && L_curr < 0) || (R_prev < 0 && L_curr > 0)) {
            ans++;
            current_sign = -current_sign;
        }

        // 2. Check for overtaking at water station i
        if (i < N) {
            int S_in = 0;
            if (L_curr > 0) S_in = 1;
            else if (L_curr < 0) S_in = -1;
            else S_in = current_sign;

            int128 R_curr = b_prime[i] - a_prime[i];
            int S_out = 0;
            if (R_curr > 0) S_out = 1;
            else if (R_curr < 0) S_out = -1;
            else S_out = (V > W) ? 1 : -1;

            // Check if their resting intervals at station i overlap
            if (a[i] <= b_prime[i] && b[i] <= a_prime[i]) {
                if (S_in != S_out) {
                    ans++;
                }
            }
            current_sign = S_out;
        }
    }

    cout << ans << "\n";

    return 0;
}

---

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