/*** * Copyright (c) Burunduk1 2006.04.08 * Random tree, implementation without pointers ***/ #include #include #include #define MAXT 65010 typedef unsigned short word; struct tree { int x; word si, L, R; }; tree T[MAXT]; int Pos = 1; void Calc( int a ) { if (!T) return; T[a].si = 1; if (T[a].L) T[a].si += T[T[a].L].si; if (T[a].R) T[a].si += T[T[a].R].si; } int NewT( int x, int L, int R ) { int a = Pos++; T[a].x = x, T[a].L = L, T[a].R = R; Calc(a); return a; } void Split( int a, word *L, word *R, int x ) { if (!a) *L = *R = 0; else if (T[a].x < x) Split(T[a].R, &T[a].R, R, x), *L = a; else Split(T[a].L, L, &T[a].L, x), *R = a; Calc(*L), Calc(*R); } void Add( word *a, int x ) { if (!*a) *a = NewT(x, 0, 0); else if (rand() % (T[*a].si + 1)) if (T[*a].x < x) Add(&T[*a].R, x); else Add(&T[*a].L, x); else { word L, R; Split(*a, &L, &R, x); *a = NewT(x, L, R); } Calc(*a); } void Merge( word *a, int L, int R ) { if (!L || !R) *a = L > R ? L : R; else if (rand() % (T[L].si + T[R].si) >= T[L].si) *a = L, Merge(&T[L].R, T[L].R, R); else *a = R, Merge(&T[R].L, L, T[R].L); Calc(*a); } void Del( word *a, int x ) { if (T[*a].x < x) Del(&T[*a].R, x); else if (T[*a].x > x) Del(&T[*a].L, x); else Merge(a, T[*a].L, T[*a].R); Calc(*a); } int Get( int a, int x ) { if (T[a].x < x) return T[a].R ? Get(T[a].R, x) : 0; if (!T[a].L) return T[a].si; return T[a].si - T[T[a].L].si + Get(T[a].L, x); } int main( void ) { char s[9]; double a; __int64 sum = 0; int k, x, n; word Root = NewT(0, 0, 0); while (scanf("%s", s) == 1 && strcmp(s, "QUIT") != 0) { scanf("%lf", &a), x = (int)(a * 100 + 1e-9); if (strcmp(s, "BID") == 0) Add(&Root, x); else if (strcmp(s, "DEL") == 0) Del(&Root, x); else { scanf("%d", &k); n = Get(Root, x); sum += k > n ? n : k; } } printf("%.2lf", sum * 0.01); return 0; }