|
|
back to boardWho can give me an ACed program? I got TLE on case #26... Posted by --- 7 Oct 2006 08:55 I use Splay Tree to store the deleted number and Binary Search on N. Re: Who can give me an ACed program? I got TLE on case #26... Posted by Thunder 22 Dec 2007 16:05 //--------------------------------------------------------------------------- #include <stdio.h> //--------------------------------------------------------------------------- int q[10001]; int GetPos(int x, int l, int r) { if (l>=r) return l; if(q[(l+r)/2]<=x) return GetPos(x,(l+r)/2+1,r); else return GetPos(x,l,(l+r)/2); } //--------------------------------------------------------------------------- int main() { int a=0; q[a]=2000000000; int n; char Key[2]; int Val; scanf("%d%d",&n,&n); for(int i=0;i<n;i++) { scanf("%s%d",&Key,&Val); if(Key[0]=='L') printf("%d\n",Val+GetPos(Val,0,a)); else { int Pos=GetPos(Val,0,a); for(int i=Pos;i<a;i++) q[i]--; for(int i=a;i>Pos;i--) q[i]=q[i-1]; q[Pos]=Val; q[++a]=2000000000; } } return 0; } //--------------------------------------------------------------------------- Re: Who can give me an ACed program? I got TLE on case #26... #include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> #include <math.h> #include <time.h> #include <limits.h> #include <assert.h> #define FAIL *(int*)0 = 0 int a[16384]; int l[16384]; int r[16384]; int p[16384]; int h[16384]; int v[16384]; int root = -1; int nn; int n, m; inline void upd(int x) { h[x] = 0; v[x] = 1; if(l[x]>=0) { if(h[l[x]]+1 > h[x]) h[x] = h[l[x]]+1; v[x] += v[l[x]]; } if(r[x]>=0) { if(h[r[x]]+1 > h[x]) h[x] = h[r[x]]+1; v[x] += v[r[x]]; } } void fix(int x) { while(x>=0) { int h1 = l[x]>=0 ? h[l[x]]+1 : 0; int h2 = r[x]>=0 ? h[r[x]]+1 : 0; if(h1 > h2+1 || h1==h2+1 && p[x]>=0 && r[p[x]]==x) { int a = l[x]; int b = r[a]; p[(p[x]>=0 ? l[p[x]]==x ? l[p[x]] : r[p[x]] : root) = a] = p[x];
p[r[a]=x]=a; if((l[x]=b)>=0) p[b] = x, x = b; } else if(h2 > h1+1 || h2==h1+1 && p[x]>=0 && l[p[x]]==x) { int a = r[x]; int b = l[a]; p[(p[x]>=0 ? l[p[x]]==x ? l[p[x]] : r[p[x]] : root) = a] = p[x]; p[l[a]=x]=a; if((r[x]=b)>=0) p[b] = x, x = b; } else { upd(x), x = p[x]; } } } void add(int vv) { int x; if(root==-1) { p[root = nn++] = -1, x = root; } else { x = root; for(;;) { assert(vv != a[x]); if(vv < a[x]) { if(l[x]==-1) { p[l[x]=nn++]=x, x=l[x]; break; } x = l[x]; } else { if(r[x]==-1) { p[r[x]=nn++]=x, x=r[x]; break; } x = r[x]; } } } l[x] = r[x] = -1; a[x] = vv; fix(x); } inline int get(int vv) { vv--; int cl = 1, cr = n;
for(int x=root;x>=0;) { int nsl = a[x] - cl - (l[x]>=0 ? v[l[x]] : 0); if(vv < nsl) cr = a[x]-1, x = l[x]; else vv -= nsl, cl = a[x]+1, x = r[x]; } return cl+vv; } char c[128*1024]; int x[128*1024]; int main() { // freopen("input.txt", "r", stdin); scanf("%d %d", &n, &m); int i; for(i=0;i<m;i++) { char ts[4]; scanf("%s %d", ts, x+i), c[i] = ts[0]; } for(i=0;i<m;i++) { if(c[i]=='D') add(get(x[i])); else if(c[i]=='L') printf("%d\n", get(x[i])); }
return 0; } Edited by author 12.08.2008 10:18 Re: Who can give me an ACed program? I got TLE on case #26... P.S: This is my custom AVL tree with only two simmetrical cases, specially for contests :) (though it can perform at log^2(N), this rarely happens) Edited by author 12.08.2008 10:17 |
|
|