[BOJ/백준][Platinum5] 2568 : 전깃줄 - 2 (C++)

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

2568번: 전깃줄 - 2

 

 

[난이도] Platinum5
[유형] DP

[풀이]
O(nlogn) LIS 문제입니다.

 

#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
int N,mp[500001],pos[100001];
pair<int,int> a[100001];
set<int> ans;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) {
        scanf("%d%d",&a[i].first,&a[i].second);
        ans.insert(a[i].first);
    }
    sort(a,a+N);
    for(int i=0;i<N;i++) mp[a[i].second]=i;

    vector<int> v;
    for(int i=0;i<N;i++){
        int idx = lower_bound(v.begin(),v.end(),a[i].second)-v.begin();
        if(v.size()==idx) v.push_back(a[i].second);
        else v[idx]=a[i].second;
        pos[i]=idx;
    }
    int k=v.size()-1;
    for(int i=N-1;i>=0;i--){
        if(pos[i]==k){
            ans.erase(a[i].first);
            if(--k<0) break;
        }
    }
    printf("%d\n",ans.size());
    for(auto k : ans) printf("%d\n",k);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Platinum5/2568.cpp