Overview

When runners are sorted in ascending order of their initial positions \(P_i\), the number of overtakes equals the “number of inversions in the speed sequence \(V_i\).” Thus, the problem reduces to efficiently counting inversions.

Analysis

Key Insight

For runners \(i, j\), suppose \(P_i < P_j\) (\(i\) is behind, \(j\) is ahead). Their positions at time \(t\) are: - \(i\): \(P_i + V_i t\) - \(j\): \(P_j + V_j t\)

An “overtake” occurs when, for some \(t > 0\): [ P_i + V_i t > P_j + V_j t ] Rearranging: [ (V_i - V_j)t > P_j - P_i ] Since the right-hand side satisfies \(P_j - P_i > 0\):

• If \(V_i > V_j\), then \(t = \dfrac{P_j - P_i}{V_i - V_j} > 0\) exists, and an overtake will definitely occur once.
• If \(V_i < V_j\), then the left-hand side is always \(\le 0\), so no overtake can happen.

Since the constraints guarantee all speeds are distinct, there are no cases of equal speeds preventing overtakes or runners running side by side indefinitely.

Therefore, the number of overtakes = the number of pairs where a runner starts behind but has a faster speed: [ #{(i,j)\mid P_i < P_j \ \text{and}\ V_i > V_j} ]

Why the Naive Approach Fails

Checking all pairs \((i,j)\) takes \(O(N^2)\), which is far too slow for \(N \le 2\times 10^5\).

How to Solve It

By sorting by \(P\) to fix the “initial position order,” the problem becomes simply counting the number of inversions in the speed sequence \(V\). Inversions can be counted in \(O(N\log N)\) using a Fenwick tree (BIT).

(Example) If the speeds in ascending order of \(P\) are \([4,1,3]\), the inversions are \((4,1),(4,3)\) — 2 inversions → 2 overtakes.

Algorithm

1. Sort the runners in ascending order of initial position \(P_i\).
2. In that order, construct the speed sequence \(V_1, V_2, \dots, V_N\).
3. Since speeds can be up to \(10^9\), they cannot be used directly as BIT indices. Therefore, sort the speeds in ascending order and apply coordinate compression, converting each speed \(V\) to a rank in \(1..N\).
4. Process the speed ranks from left to right, recording “the count of speeds seen so far” in the BIT:
   • Let \(r\) be the current speed rank
   • Let seen be the number of speeds processed so far
   • Using the BIT prefix sum, compute “the count of speeds \(\le r\) seen so far” as leq = sum(r), then:
     • The count of previously seen speeds greater than the current one is seen - leq
     • This is exactly the number of new inversions (= overtake pairs) added
   • Then add \(r\) to the BIT with a count of 1

This gives us the total number of inversions (overtakes).

Complexity

• Time complexity: \(O(N\log N)\) (two sorts + \(N\) BIT updates/queries)
• Space complexity: \(O(N)\) (arrays, BIT, coordinate compression)

Implementation Notes

• Coordinate compression: Since all speeds are distinct, we can use a dictionary rank = {v: i+1} for a unique mapping (1-indexed works well with BIT).

• BIT usage:

  • sum(r) returns “the count of occurrences with rank \(\le r\)”
  • seen - sum(r) gives “the count of occurrences with rank \(> r\)” = the additional inversions

• Since the input is large, sys.stdin.buffer.read() is used for fast input reading.

  Source Code

import sys

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, i, x):
        while i <= self.n:
            self.bit[i] += x
            i += i & -i

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    n = data[0]
    runners = []
    idx = 1
    for _ in range(n):
        p = data[idx]; v = data[idx + 1]
        idx += 2
        runners.append((p, v))

    runners.sort()  # by position
    vs = [v for _, v in runners]

    sorted_vs = sorted(vs)
    rank = {v: i + 1 for i, v in enumerate(sorted_vs)}  # 1-indexed

    fw = Fenwick(n)
    inv = 0
    seen = 0
    for v in vs:
        r = rank[v]
        leq = fw.sum(r)
        inv += seen - leq
        fw.add(r, 1)
        seen += 1

    print(inv)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.