1 条题解

  • 0
    @ 2026-4-18 20:23:12

    #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
    上传者