Code:
#include <cstdio> #include <algorithm> #include <cstring> #define maxn 200000 #define setIO(s) freopen(s".in","r",stdin) using namespace std; int n,ans[maxn],hh[maxn]; inline void getmax(int &a,int b){ if(b>a)a=b; } struct Node{ int x,y,z,org; }node[maxn]; int cmpx(Node a,Node b) { if(a.x==b.x&&a.y==b.y) return a.z<b.z; else if(a.x==b.x) return a.y<b.y; else return a.x<b.x; } int cmpy(Node a,Node b){ if(a.y==b.y) return a.z<b.z; else return a.y<b.y; } struct BIT{ int C[maxn]; int lowbit(int t) { return t&(-t);} void update(int p,int x){ while(p<maxn) getmax(C[p],x),p+=lowbit(p); } int query(int p){ if(p<=0) return 0; int ss=0; while(p>0) getmax(ss,C[p]),p-=lowbit(p); return ss; } void del(int p){ while(p<maxn)C[p]=0,p+=lowbit(p); } }tree; void solve(int l,int r){ if(l>=r) return; int mid=(l+r)>>1,tl=l,tr=mid+1; solve(l,mid); sort(node+l,node+mid+1,cmpy),sort(node+mid+1,node+r+1,cmpy); while(tl<=mid&&tr<=r) { if(node[tl].y<node[tr].y) { tree.update(node[tl].z,ans[node[tl].org]); ++tl; } else { getmax(ans[node[tr].org],tree.query(node[tr].z-1)+1); ++tr; } } for(int i=tr;i<=r;++i) getmax(ans[node[i].org],tree.query(node[i].z-1)+1); for(int i=l;i<=mid;++i) tree.del(node[i].z); sort(node+mid+1,node+1+r,cmpx),solve(mid+1,r); } int main(){ //setIO("input"); scanf("%d",&n); for(int i=1;i<=n;++i) node[i].x=node[i].org=i,scanf("%d%d",&node[i].y,&node[i].z),hh[i]=node[i].z; sort(hh+1,hh+1+n); for(int i=1;i<=n;++i) node[i].z=lower_bound(hh+1,hh+1+n,node[i].z)-hh; for(int i=1;i<=n;++i) ans[i]=1; sort(node+1,node+1+n,cmpx); solve(1,n); int h=0; for(int i=1;i<=n;++i) getmax(h,ans[i]); printf("%d",h); return 0; }