Overview

This problem asks us to count how many times the sign of the difference between the positions of two people, \(f(t)-g(t)\), changes.
We simulate this by considering only the times when their velocities change (such as arriving at a water station or finishing a rest) as events.

Analysis

Since the positions of the two people are continuous with respect to time and they move at a constant speed in each interval, the position difference \(f(t)-g(t)\) is a piecewise linear function.
Therefore, during any interval where their velocities do not change, the sign can change at most once.

Issues with a Naive Approach

If we use the actual time as-is, the travel time between water stations is:

• Takahashi: \(\frac{1}{V}\) seconds
• Aoki: \(\frac{1}{W}\) seconds

which introduces a large number of fractions.
Using floating-point numbers can cause precision issues, potentially leading to incorrect judgments when they are at exactly the same position or right at the goal time.

Furthermore, simulating by dividing time into very small steps is impossible, as the resting time can be up to \(10^9\) seconds and \(N\) can be up to \(5 \times 10^5\).

Scaling Time to Integers

To address this, we scale the time by multiplying it by \(L = VW\).

For the actual time \(t\), let the scaled time be:

\[ \tau = Lt \]

In this case, the scaled time required to travel a distance of \(1\) between water stations is:

• Takahashi: \(\frac{1}{V} \times VW = W\)
• Aoki: \(\frac{1}{W} \times VW = V\)

which are both integers.

Additionally, a resting time of \(x\) seconds becomes:

\[ x \times VW \]

after scaling.

This allows us to manage all event times as integers.

Managing the Position Difference as Integers

Instead of the position difference itself, we consider:

\[ H(\tau) = L(f(t)-g(t)) \]

Since \(L\) is positive, the sign of \(H(\tau)\) is the same as the sign of \(f(t)-g(t)\).

Furthermore, the slope of \(H\) with respect to the scaled time \(\tau\) is:

• \(+V\) if Takahashi is running, and \(0\) if he is resting.
• \(-W\) if Aoki is running, and \(0\) if he is resting.

In other words, the change in \(H\) in a certain interval can be calculated as:

\[ (\text{Takahashi's speed} - \text{Aoki's speed}) \times \Delta \tau \]

Algorithm

First, we calculate the arrival times of both runners at the goal in scaled time.

Takahashi’s arrival time at the goal is:

\[ NW + L\sum_{i=1}^{N-1} R_i \]

Aoki’s arrival time at the goal is:

\[ NV + L\sum_{i=1}^{N-1} S_i \]

Since they do not stop at water station \(N\) (the goal), we do not include \(R_N\) and \(S_N\).

The end time of the observation is the maximum of these two:

\[ T_{\text{end}} = \max(\text{Takahashi's arrival time}, \text{Aoki's arrival time}) \]

Next, we maintain the following for each runner:

• Whether they are currently running or resting
• The time when their state will change next
• The index of the water station they have already arrived at

The events where states change are:

• Arriving at a water station
• Finishing a rest and starting to run again
• Arriving at the goal

Let the current time be cur and the next event time be nxt.
Since the velocities of both runners do not change in the interval \([cur, nxt]\), \(H\) is a linear function in this interval.

If we denote the values at the start and end of this interval as \(h\) and \(h_1\) respectively, we have:

\[ h_1 = h + (\text{Takahashi's current speed} - \text{Aoki's current speed}) \times (nxt-cur) \]

How to Count Sign Changes

An overtaking occurs when the sign of \(H\) changes from positive to negative, or from negative to positive.

However, since \(H=0\) can persist for a while, simply looking at the signs of adjacent times is not sufficient.

Therefore, we maintain the last non-zero sign that appeared as prev.

• prev = 1: Takahashi was ahead last
• prev = -1: Aoki was ahead last
• prev = 0: The relative order has not been determined yet

If a new non-zero sign appearing in an interval is different from prev, it means an overtaking has occurred once.

For example:

Positive -> 0 continues -> Negative

In this case, the sign changed from positive to negative, so it is counted as \(1\) overtaking.

On the other hand:

Positive -> 0 continues -> Positive

In this case, the relative order did not change, so it is not an overtaking.

Also, at time \(0\), both are at the same position, but one of them pulling ahead immediately after departure is not counted as an overtaking, so we initially set prev = 0.

Processing Within an Interval

Since \(H\) is a linear function within each interval, the way signs appear is limited:

• \(h = 0\), \(h_1 \neq 0\)
  The sign sign(h1) starts appearing from the middle of the interval.
• \(h \neq 0\), \(h_1 = 0\)
  The sign sign(h) continues until the end of the interval.
• \(h, h_1\) have the same sign
  That sign continues.
• \(h, h_1\) have different signs
  Since it crosses \(0\) once within the interval, \(1\) overtaking occurs.

By repeating this for each event, we can find the total number of overtakings.

Complexity

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

For each runner, we only process their arrival at each water station and the end of their rests at most once, so the number of events is \(O(N)\).

Implementation Points

• Do not use floating-point numbers; scale the time by multiplying by \(VW\) and handle everything as integers.

• Since they do not stop at water station \(N\) (the goal), ignore \(R_N\) and \(S_N\).

• If the sign changes exactly at time \(T_{\text{end}}\), it is not counted as an overtaking.

• Events for both runners can occur at the same time, so we process both events at the same cur.

• Since the values can become extremely large, while it is fine in Python, in languages like C++ they might exceed the limit of long long and require __int128 or similar.

  Source Code

import sys

def main():
    input = sys.stdin.buffer.readline

    N, V, W = map(int, input().split())
    R = list(map(int, input().split()))
    S = list(map(int, input().split()))

    L = V * W

    finish_t = (sum(R) - R[-1]) * L + N * W
    finish_a = (sum(S) - S[-1]) * L + N * V
    T_end = finish_t if finish_t >= finish_a else finish_a
    INF = T_end + 1

    cur = 0
    h = 0
    ans = 0
    prev = 0

    k_t = 0
    k_a = 0

    vel_t = V
    vel_a = W

    step_t = W
    step_a = V

    next_t = step_t
    next_a = step_a

    while cur < T_end:
        nxt = next_t if next_t < next_a else next_a
        if nxt > T_end:
            nxt = T_end

        dt = nxt - cur
        slope = vel_t - vel_a
        h1 = h + slope * dt if slope else h

        if h == 0:
            if h1 != 0:
                sgn = 1 if h1 > 0 else -1
                if prev != 0 and prev != sgn:
                    ans += 1
                prev = sgn
        elif h1 == 0:
            sgn = 1 if h > 0 else -1
            if prev != 0 and prev != sgn:
                ans += 1
            prev = sgn
        else:
            s0 = 1 if h > 0 else -1
            s1 = 1 if h1 > 0 else -1
            if s0 == s1:
                if prev != 0 and prev != s0:
                    ans += 1
                prev = s0
            else:
                if prev != 0 and prev != s0:
                    ans += 1
                ans += 1
                prev = s1

        h = h1
        cur = nxt

        if cur == T_end:
            break

        if next_t == cur:
            if vel_t:
                k_t += 1
                if k_t == N:
                    vel_t = 0
                    next_t = INF
                else:
                    r = R[k_t - 1]
                    if r:
                        vel_t = 0
                        next_t = cur + r * L
                    else:
                        next_t = cur + step_t
            else:
                vel_t = V
                next_t = cur + step_t

        if next_a == cur:
            if vel_a:
                k_a += 1
                if k_a == N:
                    vel_a = 0
                    next_a = INF
                else:
                    s = S[k_a - 1]
                    if s:
                        vel_a = 0
                        next_a = cur + s * L
                    else:
                        next_a = cur + step_a
            else:
                vel_a = W
                next_a = cur + step_a

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.