点 \(i\) が条件を満たすことは \(j\neq i\) に対し \(X_j < X_i\) ならば \(Y_j > Y_i\) が成り立つことと同値です。

したがって、\(N\) 個の点を \(X\) の昇順にソートした時に、全ての \(1\le j < i\) に対し \(Y_j > Y_i\) が成り立つような \(1\le i\le N\) の個数を求めれば良いです。

これは以下のアルゴリズムで答えを求めることができます：

• \((X_i,Y_i)\) を \(X_i\) の昇順にソートする。
• \(\text{ans}=0,Y_{\text{min}}=N+1\) とする。それぞれ条件を満たす \(i\) の個数、\(j<i\) に対する \(Y_j\) の最小値を意味する。
• \(i=1,2,\ldots,N\) に対して以下を行う：
  • \(Y_{\text{min}} > Y_i\) ならば \(\text{ans}\) に \(1\) を足す。
  • \(Y_{\text{min}}\) を \(\min(Y_{\text{min}},Y_i)\) に更新する。
• \(\text{ans}\) が求める答えである。

以上のアルゴリズムを適切に実装することでこの問題に正答することができます。計算量は \(O(N\log N)\) です。

実装例(Python3)

import sys

input = sys.stdin.readline
n = int(input())
xy = []
for i in range(n):
    x, y = map(int, input().split())
    xy.append((x - 1, y - 1))
xy.sort()
min_val = n
ans = 0
for x, y in xy:
    min_val = min(min_val, y)
    ans += min_val == y
print(ans)