1503: [NOI2004]郁闷的出纳员 - #include <Seter> - using namespace Orz;
1503: [NOI2004]郁闷的出纳员
http://www.zybbs.org/JudgeOnline/problem.php?id=1503
| RunID | User | Problem | Result | Memory | Time | Language | Code Length | Submit Time |
| 170236 | Seter | 1503 | Accepted | 7980 kb | 492 ms | C/Edit | 2178 B | 2011-11-04 07:48:10 |
这几天在学Splay，果断被虐成傻X……一开始看ZKW的Splay，信心满满写自顶向下的非递归Splay，结果每次写了一半都感觉自己完全看不懂ZKW在干吗，然后全部删掉……
就这么浪费1天之后终于下决心不写自顶向下的Splay了（反正LCT不会用到！），于是自己YY了一个Splay！一开始先交了1588《营业额统计》（这题很久以前用TreapA过，但是现在调用time函数会RE所以……），结果各种WA……改了N久感觉真心没写错啊，于是和自己的Treap对拍，也没错……然后看自己的Treap代码，然后就想起来有人告诉过我这题数据不全……丢失的部分用0来替代就可以了……晕啊……
接着交1503，这题更坑爹！！！也是各种WA整整半天。无奈下找了AC大神的SBT来对拍，发现如果有个员工初始工资低于工资下界，那么这个傻X根本不会来，也就是离开的人数中不算他！！！这是我的语文问题还是出数据的人的语文问题啊！！！这种题考试的时候怎么办啊啊啊！
50+行代码，好长好坑爹……不过挺快的，比CQF说的巨快的SBT快好多……不过比RP不低的Treap还是差了点……
PS:1588HH神犇直接单旋伪splay秒杀，Orz！
接下来要学DLX和LCT……郁闷……
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | #include <stdio.h>#include <string.h>#define maxn 100001#define lt(a,b) ((a)==(b))#define rcmp(a,b) ((a)>(b))#define icmp(a,b) ((a)>=(b))#define scmp(a,b) ((a)<(b))typedef struct _Splay{struct _Splay *c[2],*f;int v,s,k;}Splay,*PSplay;Splay null,st[maxn],*stp=st,*r=&null;int ans,as,n,m,k;char str[5000000],*p=str,ch;inline PSplay update(PSplay x){return x->s=x->c[0]->s+x->c[1]->s+x->k,x;}inline PSplay rot(PSplay x){ PSplay fx=x->f,ffx=fx->f; _Bool c=fx->c[1]==x,fc=ffx->c[1]==fx; if(fx!=&null){ if(fx->c[c]=x->c[!c])fx->c[c]->f=fx; if((x->f=ffx)!=&null)ffx->c[fc]=x; update((fx->f=x)->c[!c]=fx); }return x;}inline PSplay splay(PSplay x){ if(x==&null||x->f==&null)return x; for(;x->f!=&null;rot(x))if(x->f->f!=&null)rot((x->f->f->c[1]==x->f)==(x->f->c[1]==x)?x->f:x); return update(x);}inline PSplay Rank(PSplay r,int x){ _Bool c; if(x<=0||r->s<x)return &null; for(;;r=r->c[c])if(x>r->c[0]->s&&x<=r->c[0]->s+r->k)return splay(r);else if(c=x>r->c[0]->s)x-=r->c[0]->s+r->k;}inline PSplay Find(PSplay r,int x){ PSplay ans=&null; for(;r!=&null;r=r->c[rcmp(r->v,x)])if(icmp(r->v,x)&&(ans==&null||scmp(r->v,ans->v)))ans=r; return splay(ans);}inline PSplay Insert(PSplay r,int x){ for(stp->f=&null;r!=&null;r=(stp->f=r)->c[rcmp(r->v,x)])if(lt(r->v,x)){r->s++,r->k++;return splay(r);} stp->v=x;stp->c[0]=stp->c[1]=&null;stp->s=stp->k=1; return stp->f==&null?stp++:splay(stp->f->c[rcmp(stp->f->v,x)]=stp++);}inline getint(){ int re=0; while(*p<'0'||*p>'9')if(!*p++)return -1; while(*p>='0'&&*p<='9')re=re*10+*p++-48; return re;}main(){ fread(str,1,5000000,stdin); n=getint(),m=getint();null.f=null.c[0]=null.c[1]=&null; for(r=Insert(r,~0U>>1);n--;){ ch=*++p;k=getint(); if(ch=='F'){ if(r->s<++k)puts("-1"); else printf("%d\n",(r=Rank(r,k))->v-as); }else if(ch=='A')as-=k; else if(ch=='I'){if(k>=m)r=Insert(r,k+as);} else{ ans+=(r=Find(r,(as+=k)+m))->c[1]->s; r->s-=r->c[1]->s;r->c[1]=&null; } }return printf("%d\n",ans),0;} |
By Seter
2011年11月05日 17:01
记得我是用SBT写的。用了整整一下午调试。
2011年11月06日 11:56
Orz会SBT的!!（不过总感觉这货很慢）
2022年12月29日 19:27
I was working as a cashier at a local grocery store when I started to feel depressed. I had been working there for a few months and I was starting to feel like I was in a rut. I didn't enjoy my job and I didn't feel diamond rings like I was good at it. I started to dread going to work and I would often find myself crying in the break room. I knew I needed to make a change but I didn't know what to do.