Submission #72207412

---

Source Code Expand

#include<bits/stdc++.h>
#define M 200005
#define lowbit(x) x&(-x)
using namespace std;
struct node{
	int x,y;
	bool operator <(const node &_)const{
		return x<_.x;
	}
}A[M];
int B[M];
void check_max(int &x,int y){
	if(x<y)x=y;
}
struct Bin{
	int num[M];
	void Clear(){
		memset(num,0,sizeof(num));
	}
	void Add(int x,int d){
		x++;
		while(x<M){
			check_max(num[x],d);
			x+=lowbit(x); 
		}
	}
	int Query(int x){
		x++;
		int res=0;
		while(x){
			check_max(res,num[x]); 
			x-=lowbit(x);
		}
		return res;
	}
}BT;
int dp[M];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d%d",&A[i].x,&A[i].y);
	for(int i=1;i<=n;i++)B[i]=A[i].x;
	sort(B+1,B+n+1);
	int sz=unique(B+1,B+n+1)-B-1;
	for(int i=1;i<=n;i++)A[i].x=lower_bound(B+1,B+sz+1,A[i].x)-B;
	
	for(int i=1;i<=n;i++)B[i]=A[i].y;
	sort(B+1,B+n+1);
	sz=unique(B+1,B+n+1)-B-1;
	for(int i=1;i<=n;i++)A[i].y=lower_bound(B+1,B+sz+1,A[i].y)-B;
	sort(A+1,A+n+1);
	int ans=0;
	BT.Clear();
	for(int i=1;i<=n;i++){
		int j=i;
		while(j<n&&A[j+1].x==A[i].x)j++;
		for(int k=i;k<=j;k++){
			dp[k]=BT.Query(A[k].y-1)+1;
			check_max(ans,dp[k]);
		}
		for(int k=i;k<=j;k++){
			BT.Add(A[k].y,dp[k]);
		}
		i=j;
	}
	printf("%d\n",ans);
	return 0;
}

Submission Info

Judge Result