2568번: 전깃줄 - 2

https://www.acmicpc.net/problem/2568


$O(n\lg n)$

한 쪽 번호를 기준으로 정렬한뒤 다른 한 쪽 번호를 이용해 최장증가수열을 구한다. 이 수열에 포함되지 않는 전깃줄을 제거한다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int MXN = 1e5, MXI = 5e5;
pair<int, int> p[MXN];
int n, sz, dp[MXN], fr[MXI + 1], ck[MXI + 1];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d %d", &p[i].first, &p[i].second);
    sort(p, p + n);
    for (int i = 0; i < n; i++) {
        int h = lower_bound(dp, dp + sz, p[i].second) - dp;
        if (h == sz) sz++;
        dp[h] = p[i].second;
        fr[dp[h]] = h ? dp[h - 1] : 0;
    }
    printf("%d\n", n - sz);
    for (int i = dp[sz - 1]; i; i = fr[i]) ck[i] = 1;
    for (int i = 0; i < n; i++) if (!ck[p[i].second]) printf("%d\n", p[i].first);
    return 0;
}