Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
52608 heaksicn 木板游戏 C++ 解答错误 75 182 MS 11968 KB 1231 2022-07-19 14:11:17

Tests(15/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){ 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){ 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; }


测评信息: