Overview

Given \(N\) runners with their positions and velocities, we need to find the total number of “overtakes” that occur during the race. This can be reduced to finding the inversion count.

Analysis

Conditions for an Overtake to Occur

For runner \(i\) to overtake runner \(j\), the following two conditions must be satisfied simultaneously:

1. At time \(0\), runner \(i\) is behind runner \(j\): \(P_i < P_j\)
2. At some time \(t > 0\), runner \(i\) is ahead of runner \(j\)

Expressing the second condition mathematically: $\(P_i + V_i \times t > P_j + V_j \times t\)\( \)\(V_i \times t - V_j \times t > P_j - P_i\)\( \)\((V_i - V_j) \times t > P_j - P_i\)$

Since \(P_j - P_i > 0\) (from condition 1), for a positive time \(t\) satisfying this inequality to exist, we need \(V_i > V_j\).

Reformulating the Problem

In the end, the conditions for a pair \((i, j)\) where an overtake occurs are: - \(P_i < P_j\) (\(i\) is behind) and \(V_i > V_j\) (\(i\) is faster)

In other words, we need to count the number of pairs where the order of positions and the order of velocities are inverted.

Problem with the Naive Approach

Checking all pairs \((i, j)\) requires \(O(N^2)\) time, which is too slow for \(N = 2 \times 10^5\) (approximately \(4 \times 10^{10}\) operations would be needed).

Reduction to Inversion Count

Sort the runners in ascending order of position \(P\). Let the velocity sequence after sorting be \(V_1', V_2', \ldots, V_N'\): - Index \(i < j\) means “the \(i\)-th runner was behind” - \(V_i' > V_j'\) means “the runner who was behind is faster”

Therefore, the inversion count of the velocity sequence (the number of pairs where \(i < j\) and \(V_i' > V_j'\)) is the answer.

Algorithm

We use counting inversions with merge sort.

1. Sort the runners in ascending order of initial position \(P\)
2. Extract the velocity sequence after sorting
3. Count inversions while performing merge sort on the velocity sequence

How merge sort counts inversions: - Split the array into left and right halves, recursively sort each - During merging, when an element from the right side is selected first (right element < remaining left elements), inversions exist with all remaining elements on the left side - Therefore, each time an element is selected from the right side, add “the number of remaining elements on the left side” to the inversion count

Concrete Example

Consider 3 runners with the following positions and velocities: - Runner A: position=10, velocity=5 - Runner B: position=5, velocity=8
- Runner C: position=15, velocity=3

After sorting by position: B(5), A(10), C(15) Velocity sequence: [8, 5, 3]

Inversions: (8,5), (8,3), (5,3) — 3 pairs → the answer is 3

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting takes \(O(N \log N)\)
  • Counting inversions with merge sort takes \(O(N \log N)\)
• Space complexity: \(O(N)\)
  • Storage for runner information and working space for merge sort

Implementation Notes

• In the merge sort implementation, when selecting an element from the right side, add len(left) - i (the number of remaining elements on the left side) to the inversion count

• A stable sort is not required, and since it is guaranteed that no duplicate values exist, there are no issues

• In Python, attention to recursion depth is needed, but with \(N \leq 2 \times 10^5\), the recursion depth is approximately \(\log_2 N \approx 18\), so there is no problem

  Source Code

import sys

def merge_sort_count(arr):
    if len(arr) <= 1:
        return arr, 0
    
    mid = len(arr) // 2
    left, left_inv = merge_sort_count(arr[:mid])
    right, right_inv = merge_sort_count(arr[mid:])
    
    merged = []
    inversions = left_inv + right_inv
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            inversions += len(left) - i
            j += 1
    
    merged.extend(left[i:])
    merged.extend(right[j:])
    
    return merged, inversions

def solve():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx])
    idx += 1
    
    runners = []
    for i in range(N):
        P = int(input_data[idx])
        V = int(input_data[idx + 1])
        idx += 2
        runners.append((P, V))
    
    # Sort by initial position (descending) - runner in front first
    # For runner i to overtake runner j:
    # - At time 0: P_i < P_j (i is behind j)
    # - At some time t > 0: P_i + V_i * t > P_j + V_j * t
    # This means V_i > V_j (i is faster than j)
    
    # So we need to count pairs (i, j) where P_i < P_j and V_i > V_j
    # This is counting inversions when we sort by position and look at velocities
    
    # Sort runners by position in ascending order
    runners.sort(key=lambda x: x[0])
    
    # Extract velocities in order of increasing position
    velocities = [v for p, v in runners]
    
    # Count inversions in velocities array
    # An inversion (i, j) where i < j and velocities[i] > velocities[j]
    # means: runner at position i (smaller position) has higher velocity
    # So runner at smaller position will overtake runner at larger position
    
    _, count = merge_sort_count(velocities)
    
    print(count)

solve()

---

This editorial was generated by claude4.5opus.