問題文中に明記されているとおり、ランナー \(i\) がランナー \(j\) を追い越すための必要十分条件は、「時刻 \(0\) にランナー \(i\) がランナー \(j\) より後ろにいて、ランナー \(i\) の方がランナー \(j\) より早いこと」すなわち「\(P_i<P_j\) かつ \(V_i >V_j\)」です。

ランナーを \(P\) の昇順に並び替えることで、この条件は「\(i<j\) かつ \(V_i<V_j\)」となり、このような組の個数は \(V\) の転倒数の定義に一致します。よって、座標圧縮したのち、Binary Indexed Treeやセグメントツリーを用いることで答えを求めることができます。

計算量は \(O(N\log N)\) です。

実装例 (C++)

#include<bits/stdc++.h>
#include <atcoder/fenwicktree>
using namespace std;
int main(){
  int n;
  cin >> n;
  vector<pair<int,int>>pv(n);
  for(int i=0; i<n; i++) cin >> pv[i].first >> pv[i].second;
  sort(pv.begin(), pv.end());

  set<int>s;
  for(int i=0; i<n; i++){
    s.insert(pv[i].second);
  }
  vector<int>i2v(s.begin(), s.end());
  map<int,int>v2i;
  for(int i=0; i<i2v.size(); i++){
    v2i[i2v[i]] = i;
  }

  long long ans = 0;
  int L = i2v.size();
  atcoder::fenwick_tree<int>seg(L);
  for(int i=0; i<n; i++){
    int ii = v2i[pv[i].second];
    ans += seg.sum(ii+1, L);
    seg.add(ii, 1);
  }
  cout << ans << endl;
}

実装例 (Python)

from atcoder.fenwicktree import FenwickTree

N = int(input())
PV = []
for _ in range(N):
  p, v = map(int,input().split())
  PV.append((p, v))
PV.sort()

i2v = sorted(set(v for _, v in PV))
v2i = {v:i for i, v in enumerate(i2v)}

ans = 0
L = len(i2v)
seg = FenwickTree(L)
for _, v in PV:
  i = v2i[v]
  ans += seg.sum(i+1, L)
  seg.add(i, 1)
print(ans)

なお、C++であればgcc拡張の ext/pb_ds/assoc_container.hpp にある __gnu_pbds::tree 、python であれば sortedcontainers の SortedList により、要素の追加・削除・「xより小さい要素は何個あるか求める」を直接行えるデータ構造を使うこともできます。

実装例 (C++)

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
int main(){
  int n;
  cin >> n;
  vector<pair<int,int>>pv(n);
  for(int i=0; i<n; i++) cin >> pv[i].first >> pv[i].second;
  sort(pv.begin(), pv.end());
  
  long long ans = 0;
  tree<
    int,
    null_type,
    less<int>,
    rb_tree_tag,
    tree_order_statistics_node_update
  > t;
  for(int i=0; i<n; i++){
    ans += t.size() - t.order_of_key(pv[i].second);
    t.insert(pv[i].second);
  }
  cout << ans << endl;
}

実装例 (Python)

from sortedcontainers import SortedSet

N = int(input())
PV = []
for _ in range(N):
  p, v = map(int,input().split())
  PV.append((p, v))
PV.sort()

S = SortedSet()
ans = 0
for _, V in PV:
  ans += len(S) - S.bisect_left(V)
  S.add(V)

print(ans)