백준 BOJ 2568 - 전깃줄 - 2

nlogn lis의 경로추적 반전 문제.

 

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

2568번: 전깃줄 - 2

lis잘 구해서 역추적 해준 다음에

역추적해서 나온 값들 정렬해주고 

입력 배열과 비교해가며

없는애들을 따로 관리해주면 된다.

 

#include <bits/stdc++.h>
#define INF 123456789
using namespace std;

vector<int> lis;
vector<pair<int,int>> v;
vector<pair<int,int>> back;
int chk[567890] = {0};
int conv[567890] = {0};
int chk2[567890] = {0};
vector<int> ans;

int main(){
	int n,a,b;
	scanf("%d", &n);
	for(int i=0; i<n; i++){
		scanf("%d %d", &a, &b);
		v.push_back({a,b});
		conv[b] = a;
	}
	
	sort(v.begin(), v.end());
	lis.push_back(-INF);
	for(int i=0; i<n; i++){
		if(lis.back() < v[i].second){
			lis.push_back(v[i].second);
			back.push_back({lis.size()-1, v[i].second});
		}
		else{
			auto it = lower_bound(lis.begin(), lis.end(), v[i].second);
			*it = v[i].second;
			back.push_back({it - lis.begin(), v[i].second});
		}
	}
	
	printf("%d\n", n-lis.size()+1);
	int ptr = lis.size()-1;
	for(int i=n-1; i>=0; i--){
		if(back[i].first == ptr){
			chk[conv[back[i].second]]= 1;
			ptr--;
		}
	}
	
	vector<int> tmp;
	for(int i=0; i<n; i++){ if(chk[v[i].first]) tmp.push_back(v[i].first); }
	sort(tmp.begin(), tmp.end());
	
	int ptr2 = 0;
	for(int i=0; i<n; i++){
		if(v[i].first == tmp[ptr2]){
			ptr2++;
		}else{
			ans.push_back(v[i].first);
		}
	}
	
	for(int i=0; i<ans.size(); i++) printf("%d\n", ans[i]);
	return 0;
}