1 条题解
-
0

#include<cstdio> #include<algorithm> #define N 30010 int n,i,j,x,y,b[N],bit[N],f[N],ans; struct P{int x,y;}a[N]; inline bool cmp(P a,P b){return a.x<b.x;} inline void up(int&a,int b){if(a<b)a=b;} inline void ins(int x,int y){for(;x<=n;x+=x&-x)up(bit[x],y);} inline int ask(int x){int t=0;for(;x;x-=x&-x)up(t,bit[x]);return t;} inline int lower(int x){ int l=1,r=n,mid,t; while(l<=r)if(b[mid=(l+r)>>1]<=x)l=(t=mid)+1;else r=mid-1; return t; } inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';} int main(){ for(read(n),i=1;i<=n;i++)read(x),read(y),a[i].x=x-y,a[i].y=b[i]=-x-y; for(std::sort(a+1,a+n+1,cmp),std::sort(b+1,b+n+1),i=1;i<=n;i=j){ for(j=i;j<=n&&a[j].x==a[i].x;j++)up(ans,f[j]=ask((a[j].y=lower(a[j].y))-1)+1); for(j=i;j<=n&&a[j].x==a[i].x;j++)ins(a[j].y,f[j]); } return printf("%d",ans),0; }
- 1
信息
- ID
- 4589
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者