Overview

Given the initial positions and speeds of \(N\) runners, count the number of times a faster runner overtakes a slower runner (= overtakes).

Analysis

First, it is important to precisely understand what an “overtake” means.
When runner \(i\) is behind runner \(j\) at time \(t=0\) (i.e., \(P_i < P_j\)),
if there exists a moment \(t>0\) such that \(P_i + V_i \cdot t > P_j + V_j \cdot t\),
then we say \(i\) has overtaken \(j\).

In other words, this is the phenomenon where “the relative order of initial positions” and “the relative order of speeds are reversed.”
That is, when runners are sorted by initial position, we need to count the number of pairs where the speeds are in “reverse order.”

For example, if the order by initial position is \(A, B, C\) and their speeds satisfy \(C > A > B\), then
\(A\) overtakes \(B\), and \(C\) overtakes both \(A\) and \(B\), giving a total of 3 overtakes.

In this way, counting for each runner “the number of runners ahead of them who are slower” reduces to counting the Inversion Number.
However, a brute-force approach takes \(O(N^2)\), which is too slow for the constraint \(N \leq 2 \times 10^5\).

Therefore, we use a Fenwick Tree (Binary Indexed Tree) as an efficient method to count inversions. This allows us to compute the answer in \(O(N \log N)\).

Algorithm

1. Read the initial position \(P_i\) and speed \(V_i\) for each runner.
2. Obtain the index sequence when runners are sorted in ascending order of initial position (pos_sorted).
3. Obtain the index sequence when runners are sorted in ascending order of speed (vel_sorted).
4. For each runner, compute the “speed rank (faster runners get lower rank)” and store it in the vel_rank array.
5. Create a list ranks by extracting only the “speed ranks” of runners in order of initial position.
6. Efficiently compute the inversion number of ranks using a Fenwick Tree:
   • Process from right to left.
   • Count the number of elements with a rank smaller than the current element using the BIT → add to the overtake count.
   • Add the current rank to the BIT.
7. The final inversion number is the answer.

Example

Input:

3
1 3
3 1
2 2

Order by initial position: Runner 1 (1m), Runner 3 (2m), Runner 2 (3m)
Speed ranks: Runner 2 (1m/s): rank 0, Runner 3 (2m/s): rank 1, Runner 1 (3m/s): rank 2

ranks = [2, 1, 0]

The inversion number of this sequence: - To the right of 2, there are 1 and 0 → 2 inversions - To the right of 1, there is 0 → 1 inversion → Total of 3 is the answer

Complexity

• Time complexity: \(O(N \log N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Sort by initial position and speed respectively, using runner indices as keys.

• Since the Fenwick Tree uses 1-indexed arrays, you need to add +1 like add(rank + 1, 1).

• By processing from right to left when computing the inversion number, elements already seen can be stored in the BIT.

  Source Code

import sys
from operator import itemgetter

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    runners = []
    for i in range(N):
        p = int(data[2*i + 1])
        v = int(data[2*i + 2])
        runners.append((p, v))
    
    # 初期位置でソートしたインデックス
    pos_sorted = sorted(range(N), key=lambda i: runners[i][0])
    # 速度でソートしたインデックス
    vel_sorted = sorted(range(N), key=lambda i: runners[i][1])
    
    # 速度順位を計算（速いほどrankが小さい）
    vel_rank = [0] * N
    for rank, idx in enumerate(vel_sorted):
        vel_rank[idx] = rank
    
    # 初期位置順で並べた時の速度順位のリスト
    ranks = [vel_rank[i] for i in pos_sorted]
    
    # 転倒数を計算する（Fenwick Tree使用）
    class FenwickTree:
        def __init__(self, n):
            self.n = n
            self.tree = [0] * (n + 1)
        
        def add(self, i, x):
            while i <= self.n:
                self.tree[i] += x
                i += i & -i
        
        def sum(self, i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i & -i
            return s
    
    ft = FenwickTree(N)
    inv_count = 0
    for i in range(N-1, -1, -1):
        rank = ranks[i]
        inv_count += ft.sum(rank)
        ft.add(rank + 1, 1)
    
    print(inv_count)

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.