Overview

The positions of the two people, \(f(t)\) and \(g(t)\), are piecewise linear functions that increase linearly while running and remain constant during water supply breaks.
By counting the number of times the sign of the difference \(h(t)=f(t)-g(t)\) changes, we can find the number of times they overtake each other.

Observations

While their positions are always continuous, their velocities change only at the following timings:

• When arriving at a water station
• When finishing a break and restarting

In other words, between these “event times”, the velocities of both runners are constant.
Therefore, in each interval,

\[ h(t)=f(t)-g(t) \]

is also a linear function.

The sign changes of a linear function can be determined simply by looking at the signs at both ends of the interval.

For example, if the signs of \(h(t)\) at the left and right ends of an interval are:

• \(+\), \(+\): no sign change
• \(-\), \(-\): no sign change
• \(+\), \(-\): exactly 1 sign change within the interval
• \(-\), \(+\): exactly 1 sign change within the interval

We also need to be careful about how to handle the times and intervals where \(h(t)=0\).

For example, if the sequence of signs is

\[ + \to 0 \to - \]

it counts as 1 overtaking, but if it is

\[ + \to 0 \to + \]

it is not an overtaking.

Therefore, we keep track of the most recent non-zero sign in chronological order. If the next non-zero sign that appears is different, we count it as 1 overtaking.

At time \(0\), both are at the same position, but this is not counted as an overtaking.
Therefore, when the first non-zero sign appears, we do not increment the count.

Also, we do not count if the sign changes exactly at the observation end time \(T\).
This can be naturally handled by not looking at any subsequent signs when the right end of the interval is \(T\) and \(h(T)=0\).

Algorithm

First, we manage the events for each runner in chronological order.

Let \(u\) be the velocity and \(A_i\) be the sequence of waiting times.

The arrival time at water station \(i\) is

\[ \frac{i}{u}+\sum_{j=1}^{i-1} A_j \]

The departure time from water station \(i\) (for \(i<N\)) is

\[ \frac{i}{u}+\sum_{j=1}^{i} A_j \]

Since they do not stop at the goal (water station \(N\)), there is no departure event at \(N\).

In each time interval, the position of a runner can be expressed in one of the following forms:

• Running:

\[ x(t)=u t - uP \]

where \(P\) is the total time spent stopped for water breaks so far.

• Stopped:

\[ x(t)=i \]

where \(i\) is the index of the water station where they are stopped.

In other words, each runner’s position can always be represented as a linear equation:

\[ x(t)=at+b \]

The processing steps are as follows:

1. Maintain the next event time for both Takahashi and Aoki.
2. Let the current time be cur.
3. Let the next event time to occur be nxt.
   • However, if it exceeds the observation end time \(T\), set nxt = T.
4. In the interval \([cur, nxt]\), since the positions of both runners are linear, \(h(t)=f(t)-g(t)\) is also linear.
5. Examine the signs of \(h(cur)\) and \(h(nxt)\).
6. Update the sequence of non-zero signs. If it differs from the most recent non-zero sign, increment the answer by \(1\).
7. Set cur = nxt and process all events occurring at that time.
8. Repeat while cur < T.

We update the signs as follows:

• Both ends are \(0\): do nothing
• Only the left end is \(0\): use the sign of the right end
• Only the right end is \(0\): use the sign of the left end
• Both ends have the same non-zero sign: use that sign
• Both ends have different non-zero signs: use the left end’s sign, then the right end’s sign in sequence

This allows us to correctly count both sign changes within an interval and sign changes at event times.

The observation end time \(T\) is the time when the slower of the two arrives at the goal.

Takahashi’s goal time is

\[ \sum_{i=1}^{N-1} R_i + \frac{N}{V} \]

Aoki’s goal time is

\[ \sum_{i=1}^{N-1} S_i + \frac{N}{W} \]

Therefore,

\[ T=\max\left( \sum_{i=1}^{N-1} R_i + \frac{N}{V}, \sum_{i=1}^{N-1} S_i + \frac{N}{W} \right) \]

\(R_N\) and \(S_N\) represent stops after the goal, so they are not used.

Complexity

For each runner, there are \(N\) arrival events and \(N-1\) departure events, totaling \(O(N)\) events.
We process these events while merging them in chronological order.

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

Implementation Points

Since terms like \(\frac{i}{V}\) and \(\frac{i}{W}\) appear in the times, they can be fractional.
If we use floating-point numbers, precision issues may arise when checking if they are at the exact same position or when determining if the time is exactly \(T\).

Therefore, we represent and manage time as a fraction:

\[ \frac{\text{num}}{\text{den}} \]

We can compare two times using:

\[ \frac{a}{b} < \frac{c}{d} \]

by checking:

\[ ad < cb \]

Also, since the values can become extremely large, long long is not sufficient.
In the implementation, we use __int128_t to prevent overflow.

Furthermore, if the waiting time is \(0\), the arrival and departure events will occur at the exact same time.
Therefore, all events occurring at the same time must be processed together, for example, using a while loop.

Source Code

#include <bits/stdc++.h>
using namespace std;

using i128 = __int128_t;

struct Time {
    i128 num;
    long long den;
    bool inf;
};

int cmpTime(const Time& a, const Time& b) {
    if (a.inf && b.inf) return 0;
    if (a.inf) return 1;
    if (b.inf) return -1;
    i128 lhs = a.num * (i128)b.den;
    i128 rhs = b.num * (i128)a.den;
    if (lhs < rhs) return -1;
    if (lhs > rhs) return 1;
    return 0;
}

Time minTime(const Time& a, const Time& b) {
    return cmpTime(a, b) <= 0 ? a : b;
}

struct Runner {
    int N;
    long long speed;
    const vector<long long>* wait;

    bool hasEvent;
    int type; // 0: arrival, 1: departure
    int station;
    i128 nextNum;

    i128 prefixWait;

    long long slope;
    i128 intercept;

    Runner(int n, long long sp, const vector<long long>& w)
        : N(n), speed(sp), wait(&w) {
        hasEvent = true;
        type = 0;
        station = 1;
        nextNum = 1;

        prefixWait = 0;
        slope = speed;
        intercept = 0;
    }

    Time nextTime() const {
        if (!hasEvent) return {0, 1, true};
        return {nextNum, speed, false};
    }

    void process(const Time& cur) {
        while (hasEvent) {
            i128 lhs = nextNum * (i128)cur.den;
            i128 rhs = cur.num * (i128)speed;
            if (lhs != rhs) break;

            if (type == 0) {
                int i = station;
                slope = 0;
                intercept = i;

                if (i == N) {
                    hasEvent = false;
                } else {
                    type = 1;
                    station = i;
                    nextNum += (i128)(*wait)[i - 1] * speed;
                }
            } else {
                int i = station;
                prefixWait += (*wait)[i - 1];

                slope = speed;
                intercept = -prefixWait * speed;

                type = 0;
                station = i + 1;
                nextNum += 1;
            }
        }
    }
};

int signAt(const Runner& t, const Runner& a, const Time& x) {
    i128 val = ((i128)t.slope - (i128)a.slope) * x.num
             + (t.intercept - a.intercept) * (i128)x.den;
    if (val > 0) return 1;
    if (val < 0) return -1;
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

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

    i128 sumR = 0, sumS = 0;
    for (int i = 0; i < N - 1; i++) {
        sumR += R[i];
        sumS += S[i];
    }

    Time finishT = {sumR * V + N, V, false};
    Time finishA = {sumS * W + N, W, false};
    Time Tobs = cmpTime(finishT, finishA) >= 0 ? finishT : finishA;

    Runner tak(N, V, R);
    Runner aok(N, W, S);

    Time cur = {0, 1, false};

    long long ans = 0;
    int lastSign = 0;

    auto feed = [&](int s) {
        if (s == 0) return;
        if (lastSign != 0 && lastSign != s) ans++;
        lastSign = s;
    };

    auto addInterval = [&](int l, int r) {
        if (l == 0 && r == 0) return;
        if (l == 0) {
            feed(r);
        } else if (r == 0) {
            feed(l);
        } else if (l == r) {
            feed(l);
        } else {
            feed(l);
            feed(r);
        }
    };

    tak.process(cur);
    aok.process(cur);

    while (cmpTime(cur, Tobs) < 0) {
        Time nxt = minTime(tak.nextTime(), aok.nextTime());
        if (cmpTime(nxt, Tobs) > 0) nxt = Tobs;

        if (cmpTime(nxt, cur) == 0) {
            tak.process(cur);
            aok.process(cur);
            continue;
        }

        int sl = signAt(tak, aok, cur);
        int sr = signAt(tak, aok, nxt);
        addInterval(sl, sr);

        cur = nxt;
        tak.process(cur);
        aok.process(cur);
    }

    cout << ans << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-high.