Overview

Given the initial positions \(P_i\) and velocities \(V_i\) of \(N\) runners, the problem asks to find the total number of “overtakes” that will occur in the future. An overtake occurs only when a runner who is initially behind another runner has a greater velocity than the runner ahead.

Analysis

Conditions for an Overtake to Occur

Consider two runners \(i\) and \(j\), where at time \(0\), runner \(i\) is behind runner \(j\) (\(P_i < P_j\)). The condition for runner \(i\) to overtake runner \(j\) at some time \(t > 0\) is that runner \(i\)’s velocity is greater than runner \(j\)’s velocity, i.e., \(V_i > V_j\).

If \(V_i < V_j\), the distance between the two increases over time, so an overtake will never occur.

Reformulating the Problem

Let’s sort all runners in ascending order of their initial positions \(P_i\). Then, counting the number of overtakes is equivalent to counting, in the resulting sequence of velocities, the number of elements to the left (with smaller initial positions) that have a larger value (higher velocity).

This reduces to the well-known problem in algorithms called the “Inversion Number”.

Naive Approach and Its Limitation

If we check whether an overtake occurs for every pair \((i, j)\), the time complexity is \(O(N^2)\). Given the constraint \(N \le 2 \times 10^5\), this will not finish within the time limit. A more efficient \(O(N \log N)\) algorithm is needed.

Algorithm

We compute the answer using the following steps:

1. Sort: Sort the runners in ascending order of their initial positions \(P_i\).
2. Coordinate Compression: Since velocity values \(V_i\) can be as large as \(10^9\), they cannot be directly used as array indices. Since only the relative ordering of velocities matters, we convert the velocities into ranks from \(1\) to \(N\) (coordinate compression).
3. Inversion Count Calculation: Using a Binary Indexed Tree (BIT) or segment tree, process the sorted velocity sequence from left to right and count inversions.
   • Let \(r\) be the rank of the current runner’s velocity.
   • Using the BIT, find the number of previously processed runners (those with smaller initial positions) whose velocity rank is greater than \(r\), and add it to the answer.
   • Register the current velocity rank \(r\) in the BIT.

Complexity

• Time Complexity: \(O(N \log N)\)
  • Sorting the runners takes \(O(N \log N)\).
  • Coordinate compression of velocities takes \(O(N \log N)\).
  • Computing the inversion count using a BIT takes \(O(N \log N)\).
• Space Complexity: \(O(N)\)
  • Memory proportional to \(N\) is used for storing runner data and managing the BIT.

Implementation Notes

• Fast I/O: Since \(N\) can be large, in Python it is faster to read all input at once using sys.stdin.read().split() or similar methods.

• Counting Inversions: When using a BIT to find “the number of elements greater than \(r\)”, it is common to compute it as “total count - count of elements less than or equal to \(r\)”.

• Coordinate Compression Dictionary: By using a dictionary (hash map) such as rank_map = {v: i + 1 for i, v in enumerate(v_sorted)}, the rank of each velocity can be looked up in \(O(1)\).

  Source Code

import sys

def solve():
    # 高速な入出力のために、すべての入力を一度に読み込み、空白で分割してリスト化します。
    # sys.stdin.read().split() は、空白、タブ、改行をすべて区切り文字として扱います。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 最初のエントリはランナーの人数 N です。
    N = int(input_data[0])
    if N == 0:
        print(0)
        return
    
    # P_i と V_i を効率的にパースしてペアにします。
    # input_data[1:2*N+1:2] は P_1, P_2, ..., P_N を抽出し、
    # input_data[2:2*N+1:2] は V_1, V_2, ..., V_N を抽出します。
    # map(int, ...) で整数に変換し、zip で (位置, 速度) のタプルのリストを作成します。
    runners = list(zip(map(int, input_data[1:2*N+1:2]), map(int, input_data[2:2*N+1:2])))
    
    # ランナーを初期位置 P_i の昇順でソートします。
    # すべての P_i は異なるため、一意な順序が得られます。
    runners.sort()
    
    # 位置の順にソートされた状態での速度のリストを抽出します。
    # 追い抜き回数を求めることは、この速度のリストにおける「転倒数」を求めることと同義です。
    # なぜなら、P_i < P_j かつ V_i > V_j のときに限り、時刻 t > 0 で追い抜きが発生するからです。
    vels = [r[1] for r in runners]
    
    # 速度の値が大きいため（最大 10^9）、座標圧縮を行います。
    # 各速度を、全速度の中での順位（1 から N）に変換します。
    v_sorted = sorted(vels)
    rank_map = {v: i + 1 for i, v in enumerate(v_sorted)}
    ranks = [rank_map[v] for v in vels]
    
    # 転倒数を計算するために Binary Indexed Tree (Fenwick Tree) を使用します。
    # bit[i] は、これまでに処理した要素のうち、順位が i であるものの個数を管理します。
    bit = [0] * (N + 1)
    total_overtakes = 0
    
    # 各速度の順位を順番に処理し、それより大きい順位が既にいくつ現れたかをカウントします。
    for i, r in enumerate(ranks):
        # BITのクエリ：現在までに処理した要素のうち、順位が r 以下のものの個数 s を求めます。
        s = 0
        idx = r
        while idx > 0:
            s += bit[idx]
            idx -= idx & (-idx)
        
        # 現在までに処理した要素の総数は i 個です。
        # そのうち順位が r 以下のものが s 個なので、r より大きいものは (i - s) 個です。
        # これが、現在処理しているランナーよりも「前にいて遅い」ランナーの数になります。
        total_overtakes += (i - s)
        
        # BITの更新：現在のランナーの順位 r を BIT に追加します。
        idx = r
        while idx <= N:
            bit[idx] += 1
            idx += idx & (-idx)
    
    # 最終的な追い抜きの総回数を出力します。
    sys.stdout.write(str(total_overtakes) + '\n')

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-preview.