ORDERSET на spoj.pl

#include <algorithm>
#include <cstdio>

const int MAXH = 18; // 262144
int tree[1<<MAXH];

void add(int index, int delta)
{
    for (int i = index; i < (1<<MAXH); i |= (i+1)) tree[i] += delta;
}

int cums(int index)
{
    int result = 0;
    for (int i = index+1; i >= 1; i &= (i+1)) result += tree[--i];

    return result;
}

int find(int sum)
{
    int i = (1<<MAXH)-1; if (tree[i] < sum) return -1;

    for (int h = MAXH-1; h >= 0; --h)
        if (tree[i - (1<<h)] >= sum) i = i - (1<<h); else sum -= tree[i - (1<<h)];

    return i;
}

const int MAXOP = 200000;
int x[MAXOP], coords[MAXOP], NC;
char op[MAXOP], tmp[2];
bool mark[MAXOP];

int main()
{
    int Q; scanf("%d", &Q);

    for (int i = 0; i < Q; ++i) { scanf("%s", tmp); op[i] = tmp[0]; scanf("%d", &x[i]); }

    std::copy(&x[0], &x[Q], &coords[0]);
    std::sort(&coords[0], &coords[Q]);
    NC = std::unique(&coords[0], &coords[Q]) - &coords[0];

    for (int i = 0; i < Q; ++i)
    {
        if (op[i] != 'K') x[i] = std::lower_bound(&coords[0], &coords[NC], x[i]) - &coords[0];

        int res;

        switch (op[i])
        {
            case 'I': if (!mark[x[i]]) { mark[x[i]] = true; add(x[i], 1); } break;
            case 'D': if (mark[x[i]]) { mark[x[i]] = false; add(x[i], -1); } break;

            case 'K': res = find(x[i]); if (res != -1) printf("%d\n", coords[res]); else printf("invalid\n"); break;
            case 'C': printf("%d\n", cums(x[i]-1)); break;
        }
    }

    return 0;
}