ABC462 C - Not Covered Points

考え方

まず、愚直に解くと、各点 $i$ に対して他の $N-1$ 個の位置全てを確認しなくてはならない。
すると、計算量が $O(N^2)$ となり、$N = 3 \times 10^5$ ではTLEする。
よって、これを高速化する。

実は、各点の番号が何番なのかは、考える必要がない。
よって、$X$ の値が小さい順に並べなおして考えることができる。
特に今回は $X$ が $1$ から $N$ までの順列なので、$X=i$ であるものを $i$ 番目にもってくればよい。

すると、問題の長方形条件は、自分より前に自分より $Y$ が小さい点が存在しないことと言い換えられる。
（$Y$ も順列なので同じ値が複数回来ることはなく、「以下」でも「未満」でもよい）
この書き換えにより、他の点を全部調べなくても今までの最小値との比較で済み、$O(N)$ で解ける。

入力例1での動作

入力を受け取る。

n: 3
(x, y): {(2, 1), (1, 3), (3, 2)}

$X$ が小さい順に点を並べると、次の順になる。

左から順に見て、これまでに見た $Y$ の最小値より小さい点を数える。

条件を満たすのは元の点 $1,2$ の $2$ 個なので、答えは $2$ となる。

注意点

特になし。

別解

特になし。