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

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; }


测评信息:

输入

                    

输出

                    

答案

                    

系统信息

exit code: 0, checker exit code: 0

输入

                    

输出

                    

答案

                    

系统信息

exit code: 0, checker exit code: 0

输入

                    

输出

                    

答案

                    

系统信息

exit code: 0, checker exit code: 0

输入

                    

输出

                    

答案

                    

系统信息

exit code: 0, checker exit code: 0

输入

                    

输出

                    

答案

                    

系统信息

exit code: 0, checker exit code: 0

输入

                    

输出

                    

答案

                    

系统信息

exit code: 0, checker exit code: 0

输入

400
127 182
117 220
254 312
164 307
260 352
136 339
252 331
74 194
156 323
122 308
99 180
183 264
224 351
132 160
268 388
187 384
156 337
200 383
92 337
8 177
37 367
115 400
75 254
13 54
130 331
110 ...

输出

27

答案

28

系统信息

exit code: 0, checker exit code: 0

输入

                    

输出

                    

答案

                    

系统信息

exit code: 0, checker exit code: 0

输入

                    

输出

                    

答案

                    

系统信息

exit code: 0, checker exit code: 0

输入

                    

输出

                    

答案

                    

系统信息

exit code: 0, checker exit code: 0

输入

                    

输出

                    

答案

                    

系统信息

exit code: 0, checker exit code: 0

输入

                    

输出

                    

答案

                    

系统信息

exit code: 0, checker exit code: 0

输入

                    

输出

                    

答案

                    

系统信息

exit code: 0, checker exit code: 0

输入

                    

输出

                    

答案

                    

系统信息

exit code: 0, checker exit code: 0

输入

                    

输出

                    

答案

                    

系统信息

exit code: 0, checker exit code: 0

输入

                    

输出

                    

答案

                    

系统信息

exit code: 0, checker exit code: 0

输入

                    

输出

                    

答案

                    

系统信息

exit code: 0, checker exit code: 0

输入

                    

输出

                    

答案

                    

系统信息

exit code: 0, checker exit code: 0

输入

                    

输出

                    

答案

                    

系统信息

exit code: 0, checker exit code: 0

输入

                    

输出

                    

答案

                    

系统信息

exit code: 0, checker exit code: 0