FOCUS - Chuyên gia ruồi

Tác giả: ladpro98

Ngôn ngữ: C++

#include <bits/stdc++.h>
#define ii pair<int, int>
#define X first
#define Y second
const int N = 200005;
const int add = 1;
const int del = -1;
const int cnt = 2;
struct e {
    int type, a, b, k;
};
using namespace std;
e event[N];
ii b[N];
int mirror[N], bit[N];
int n, m, d;

int BS(int key) {
    int l = 0, r = d, k = 0, m;
    while (l <= r) {
        m = (l + r) >> 1;
        if (mirror[m] <= key) {
            k = m; l = m + 1;
        }
        else
            r = m - 1;
    }
    return k;
}

void Upd(int i, int v) {
    while (i <= d) {
        bit[i] += v;
        i += i & (-i);
    }
}

int Get(int i) {
    int s = 0;
    while (i) {
        s += bit[i];
        i -= i & (-i);
    }
    return s;
}

void Enter() {
    scanf("%d\n", &n);
    int i; char c;

    for(i=1; i<=n; i++) {
        scanf("%c ", &c);
        if (c == '+') {
            event[i].type = add;
            scanf("%d\n", &event[i].a);
            b[++m] = ii(event[i].a, i);
        }
        if (c == '-') {
            event[i].type = del;
            scanf("%d\n", &event[i].a);
            b[++m] = ii(event[i].a, i);
        }
        if (c == '?') {
            event[i].type = cnt;
            scanf("%d %d %d\n", &event[i].k, &event[i].a, &event[i].b);
        }
    }
    sort(b+1, b+1+m);
    for(i=1; i<=m; i++) {
        if (b[i].X != b[i-1].X) d++;
        event[b[i].Y].a = d;
        mirror[d] = b[i].X;
    }
}

void Answer() {
    int i, L, R, mid, VL, res;
    for(i=1; i<=n; i++) {
        if (event[i].type != cnt)
            Upd(event[i].a, event[i].type);
        else {
            L = BS(event[i].a - 1);
            R = BS(event[i].b);
            VL = Get(L);
            if (R == 0 || Get(R) - VL < event[i].k) {
                printf("0\n"); continue;
            }
            while (L <= R) {
                mid = (L + R) >> 1;
                if (Get(mid) - VL >= event[i].k) {
                    res = mid;
                    R = mid - 1;
                }
                else
                    L = mid + 1;
            }
            printf("%d\n", mirror[res]);
        }
    }
}

int main()
{
    Enter();
    Answer();
    return 0;
}

Download