2020牛客冬休みアルゴリズム基礎合宿キャンプ第6回

Cハノータ題意:あなたにN組のデータXi YiからXn Ynの要求を満たす上のXi Yiは下の小さいXi~nよりすべて異なっているYi~nはすべて異なっています
構想:sortソート(大から小)+Dilworth定理最小グループ数は最長リットルシーケンス長に等しい.原型はミサイル迎撃貪欲+二分O(nlogn)のやり方が変形したものである.違うのは、まずソートしてから欲張ることです.また、パケットを出力する場合は、パケットは貪欲に覆われたときにマークを付けることができます.

#include
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 +7;
const ll MAXN = 1e6 + 5;

struct node{
	int x,y,z;
	bool operator < (const node X){
		return x>X.x;
	}
}a[MAXN],b[MAXN];

int c[MAXN];
int f[MAXN];


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;cin>>n;
	for(int i=1;i<=n;i++){
		cin>>b[i].x>>b[i].y;
		b[i].z=i;
		a[i].x=b[i].x;
		a[i].y=b[i].y;
		a[i].z=b[i].z;
	}
	sort(a+1,a+1+n);
 	int len=0;
	for(int i=1;i<=n;i++){
		if(a[i].y>f[len]){
			f[++len]=a[i].y;
			b[a[i].z].z=len;
		}
		else{
			*lower_bound(f+1,f+1+len,a[i].y)=a[i].y;
			int p=lower_bound(f+1,f+1+len,a[i].y)-f;
			b[a[i].z].z=p;
		}
	}
	cout<<len<<'
';
	for(int i=1;i<=n;i++) cout<<b[i].z<<" ";
	return 0;
}