Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
52610 heaksicn 木板游戏 C++ 通过 100 169 MS 11960 KB 1293 2022-07-19 14:13:46

Tests(20/20):


#include<bits/stdc++.h> using namespace std; inline int read(){ int X=0,w=0; char ch=0; while(!isdigit(ch)) {w|=ch=='-';ch=getchar();} while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X; } inline void write(int x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); } int n; struct node{ int l,r,id; }a[500001]; bool cmp(node x,node y){ if(x.r==y.r) return x.l<y.l; return x.r>y.r; } int dp[500001]; int tr[500001]; int tp=0; int lowbit(int x){ return x&(-x); } int update(int x,int y){ while(x<=tp){ tr[x]=max(tr[x],y); x+=lowbit(x); } } int query(int x){ int res=0; while(x>0){ res=max(res,tr[x]); x-=lowbit(x); } return res; } bool cp(node x,node y){ if(x.l==y.l) return x.r>y.r; return x.l<y.l; } int main(){ n=read(); for(int i=1;i<=n;i++) a[i].l=read(),a[i].r=read(); sort(a+1,a+n+1,cmp); for(int i=1;i<=n;i++){ if(a[i].r!=a[i-1].r) tp++; a[i].id=tp; } sort(a+1,a+n+1,cp); // for(int i=1;i<=n;i++)cout<<a[i].id<<" "; dp[1]=1; update(a[1].id,1); int ans=0; for(int i=2;i<=n;i++){ dp[i]=query(a[i].id)+1; update(a[i].id,dp[i]); ans=max(ans,dp[i]); } // for(int i=1;i<=tp;i++) ans=max(ans,tr[i]); write(ans); return 0; }


测评信息: