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

ハノータ
タイトルの説明
今あなたはN枚の矩形の板を持っていて、i枚目の板のサイズはXi*Yiで、あなたはこれらの板でハンノタのゲームをしたいと思っています.ハンノッタゲームをするには、いくつかの板を上下に大きく積み重ねなければならないことを知っていますが、板は矩形なので、問題があります.i番目の板はj番目の板の上に置くことができます.Xiができるだけ少ないグループに分けたい場合は、各グループ内の板を一定の順序で重ねることができます.任意の合理的なグループ化案を与える必要があります.注意:「任意」は、正しい限り、答えが標準出力と完全に一致する必要はありません.
説明を入力:
1行目、正の整数Nの次のN行、各行の2つの正の整数はXiとYiがすべてのデータに対して、1≦N≦100000、1≦Xi、Yi≦N、Xiは互いに等しくなく、Yiは互いに等しくない
出力の説明:
出力ファイルには2行が含まれています.1行目は正の整数で、最小グループ数を表します.2行目はN個の正の整数で、シナリオ内の板ごとにどのグループに分かれているかを順番に表します.番号は1から連続する整数でなければなりません.
この問題はDilworthの定理を使った.
実はこの定理を知っていて、この問題はできて、もう一つの技巧は2分が最も長い減少子のシーケンスの長さを求める時、グループを一緒に計算して、1つの要素が別の要素にその位置で取って代わることができる時、これらの要素は同じグループに分けられました;
コード:

#include
#define ll long long
#define pa pair
#define lson k<<1
#define rson k<<1|1
#define inf 0x3f3f3f3f
//ios::sync_with_stdio(false);
using namespace std;
const int N=100100;
const int M=1000100;
const ll mod=998244353;
struct Node{
	int x,y;
	int post;
}a[N];
bool cmp(Node p,Node q){
	return p.x<q.x;
}
int ans[N];
int sta[N];
int main(){
	ios::sync_with_stdio(false);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].x>>a[i].y;
		a[i].post=i;
	} 
	sort(a+1,a+1+n,cmp);
	int m=0;
	for(int i=1;i<=n;i++){
		int l=1,r=m;
		while(l<=r){
			int d=(l+r)>>1;
			if(sta[d]<a[i].y) r=d-1;
			else l=d+1;
		}
		sta[l]=a[i].y;
		if(l>m) m=l;
		ans[a[i].post]=l;
	}
	cout<<m<<endl;
	for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
	return 0;
}