NERD2

AOJ NERD2

SOL)

nx, ny = 새로운 점

좌표 평면에서 x는 지배당한다고 할수 있다. 이런 점들은 너드가 아니기 때문에

삭제를 해줘야 한다.

map에서 lower_bound(x)를 찾아보면

만약 it가 end()이거나  y의 값이 it->second보다 크다면

이 새로운 점은 지배를 당하지 않기 때문에 추가를 해줄 수 있다.

반대로 저위의 조건을 만족하지 못한다면 어느 점에게 지배를 당하는 점이 되므로

추가를 해줄 수가 없다.

만약 새로운 점을 추가 한다면 이 추가된 점이 기존에 있던 점들을 지배할 가능 성이

있으므로 기존에 있던 점들을 중 x좌표가 nx좌표보다 작은 것들은 가장 큰 녀석들

부터 재조사를 시작하여 검사를 한다.

항상 x가 좌표가 작으면 y가 크도록 정보를 저장 했으므로

if ny < it->second 반복문 종료

else it가 가르키는 점 삭제후 it를 한당 앞으로 놓고 재비교

[-] Collapse

#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;

int main(){
    int t; scanf("%d", &t);

    while (t--){
        map<int, int> coords;
        map<int, int>::iterator it, temp;
        int n, ans = 0;
        scanf("%d", &n);
        while (n--){
            int x, y; scanf("%d%d", &x, &y);
            it = coords.lower_bound(x);
            //add
            if (it == coords.end() || it->second < y) coords[x] = y;
            else{ ans += coords.size(); continue; }
            //erase
            it = coords.lower_bound(x);
            if (it == coords.begin()) {
                ans += coords.size();
                continue;
            }
            it--;
            while (true) {
                temp = it;
                if (it->second > y) break;
                if (it == coords.begin()){
                    coords.erase(it);
                    break;
                }
                else{
                    temp--;
                    coords.erase(it);
                    it = temp;
                }
            }
            ans += coords.size();
        }
        printf("%d\n", ans);
    }
}