Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
52977 AK2022071369 木板游戏 C++ 解答错误 95 501 MS 13968 KB 2355 2022-07-20 12:32:56

Tests(19/20):


#include <bits/stdc++.h> using namespace std; int n,l[114514*5],r[114514*5],a[114514*5],b[114514*5],d[114514*5],cbs[114514*5],c[114514*5],ll; bool cmpa(int x,int y) { if(l[x]!=l[y]) { return l[x]<l[y]; } else { return r[x]>r[y]; } } bool cmpb(int x,int y) { if(r[x]!=r[y]) { return r[x]>r[y]; } else { return l[x]<l[y]; } } int da[114514*5],topa=0; void puta(int w) { if(w==1) { return; } int f; if(w%2==0) { f=w/2; } else { f=(w-1)/2; } if(a[da[f]]>a[da[w]]) { swap(da[f],da[w]); puta(f); } } void cleana(int w) { if(w*2==topa) { if(a[da[w*2]]<a[da[w]]) { swap(da[w*2],da[w]); return; } } int s; if(w*2+1<=topa) { if(a[da[w*2]]>a[da[w*2+1]]) { s=w*2+1; } else { s=w*2; } if(a[da[w]]>a[da[s]]) { swap(da[w],da[s]); cleana(s); return; } } } int db[114514*5],topb=0; void putb(int w) { if(w==1) { return; } int f; if(w%2==0) { f=w/2; } else { f=(w-1)/2; } if(b[db[f]]>b[db[w]]) { swap(db[f],db[w]); putb(f); } } void cleanb(int w) { if(w*2==topb) { if(b[db[w*2]]<b[db[w]]) { swap(db[w*2],db[w]); return; } } int s; if(w*2+1<=topb) { if(b[db[w*2]]>b[db[w*2+1]]) { s=w*2+1; } else { s=w*2; } if(b[db[w]]>b[db[s]]) { swap(db[w],db[s]); cleanb(s); return; } } } int main() { scanf("%d",&n); for(int i=1; i<=n; i++) { scanf("%d%d",&l[i],&r[i]); a[i]=i; b[i]=i; } sort(a+1,a+n+1,cmpa); sort(b+1,b+n+1,cmpb); for(int i=1; i<=n; i++) { da[++topa]=i; puta(topa); db[++topb]=i; putb(topb); } for(int i=1; i<=n; i++) { d[db[1]]=da[1]; da[1]=da[topa--]; cleana(1); db[1]=db[topb--]; cleanb(1); } // for(int i=1; i<=n; i++) // { // printf("%d ",d[i]); // } // printf("\n"); for(int i=1; i<=n; i++) { if(d[i]>c[ll]) { c[++ll]=d[i]; } else { c[lower_bound(c+1,c+ll+1,d[i])-c]=d[i]; } } printf("%d\n",ll); return 0; }


测评信息: