Overview

For each checkpoint \(i\), compare “Takahashi’s arrival time” with “Aoki’s arrival time \(T_i\)”, and enumerate the checkpoint numbers where Takahashi arrives earlier (i.e., where overtaking occurs).

Analysis

The key insight is that “overtaking can be determined solely by comparing arrival times at checkpoints.” Even if the two runners are tied at some point along the course, this problem only asks whether Takahashi arrived at checkpoint \(i\) before Aoki (Takahashi’s arrival time \(<\) \(T_i\)).

Since Takahashi runs at a constant speed \(V\), if we let \(S_i\) be the cumulative distance to checkpoint \(i\) (with \(S_1 = 0\) for the first checkpoint), then Takahashi’s arrival time is: - \(S_i / V\) seconds

On the other hand, we know that Aoki arrives at checkpoint \(i\) at time \(T_i\).

Therefore, the condition to check is: - \(S_i / V < T_i\)

However, using division (especially floating-point division) here can cause WA due to precision errors. Also, \(S_i\) and \(T_i\) can become very large, so we want to compare them exactly using integers.

By multiplying both sides by \(V\) (since \(V > 0\)): - \(S_i < V \cdot T_i\)

This allows us to determine the result using only integer comparisons.

Naively “recomputing the distance to each checkpoint by summing from the beginning every time” would result in \(O(N^2)\), which causes TLE for \(N \le 2\times 10^5\). Instead, by updating the cumulative distance in a single forward pass, we achieve \(O(N)\).

(Concrete example) - With \(V=2\), \(D_1=3, D_2=1\), we get \(S_2=3, S_3=4\) - If \(T_2=2, T_3=3\), then: - \(i=2\): \(S_2 < VT_2 \iff 3 < 4\) → overtaking - \(i=3\): \(S_3 < VT_3 \iff 4 < 6\) → overtaking

Algorithm

1. Read the input (\(D_1 \ldots D_{N-1}\) and \(T_2 \ldots T_N\)).
2. Initialize the cumulative distance dist to \(0\) (this represents the distance from checkpoint \(1\)).
3. For \(i=2\) to \(N\) in order:
   • Compute \(S_i\), the distance to checkpoint \(i\), by dist += D[i-2]
   • If dist < V * T[i], then overtaking occurs at checkpoint \(i\), so add it to the answer
4. If the answer is empty, output -1; otherwise, output the checkpoint numbers in ascending order (which is the same as the traversal order).

Complexity

• Time complexity: \(O(N)\) (only a single pass)
• Space complexity: \(O(N)\) (for the input arrays and storing the output)

Implementation Notes

• The comparison should be done as \(S_i < V \cdot T_i\) instead of \(S_i / V < T_i\) to avoid precision errors.

• The values can become very large, but Python’s integers have arbitrary precision, so there is no overflow (in other languages, be careful and consider using 128-bit integers, etc.).

• Since the input can be large, using sys.stdin.buffer.read() for fast input reading is recommended.

  Source Code

import sys

def main():
    it = map(int, sys.stdin.buffer.read().split())
    N = next(it)
    V = next(it)

    D = [next(it) for _ in range(N - 1)]
    T = [0] * (N + 1)
    for i in range(2, N + 1):
        T[i] = next(it)

    ans = []
    dist = 0
    for i in range(2, N + 1):
        dist += D[i - 2]
        if dist < V * T[i]:
            ans.append(str(i))

    if ans:
        sys.stdout.write(" ".join(ans))
    else:
        sys.stdout.write("-1")

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.