ABC462C - 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)$ で解ける。

入力を受け取る。

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

x が小さい順に、y の値を並べなおす。

vec: {3, 1, 2}

最小値記録用変数と、カウンターを用意する。

mn : INF
result: 0

$0$ 番目を見る。最小値記録更新なので、カウントを $1$ 進める。

vec: {3, 1, 2}
mn : 3
result: 1

$1$ 番目を見る。最小値記録更新なので、カウントを $1$ 進める。

vec: {3, 1, 2}
mn : 1
result: 2

$2$ 番目を見る。最小値記録ではないので、何もしない。

vec: {3, 1, 2}
mn : 1
result: 2

カウンターの値が答え。

特になし。

特になし。