FOCUS - Chuyên gia ruồi

Tác giả: hieult

Ngôn ngữ: C++

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
//#include<conio.h>
#define ep 0.000001
#define maxn 200011
#define mod 1000000000
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define fi first 
#define se second

double const PI=4*atan(1);
double const oo = 1e19;

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

const int MAXN = 18;
int tr[MAXN + 1][1 << MAXN] = {0}, f[maxn] = {0};
void insert(int x){ for(int i = 0; i <= MAXN; i++) tr[i][x]++, x >>= 1;}
void eraser(int x){ for(int i = 0; i <= MAXN; i++) tr[i][x]--, x >>= 1;}
int kThElement(int k){
    int a = 0, b = MAXN;
    while(b--) a <<= 1, k -= ( tr[b][a] < k ? tr[b][a++] : 0);
    return a;
}

void update(int u, int gt)
{
    while(u <= 200000){
        f[u] += gt;
        u += u & -u;
    }
}

int get(int u){
    int res = 0;
    while(u > 0){
        res += f[u];
        u -= u & -u;
    }
    return res;
}

int k[maxn] = {0}, b[maxn], a[maxn], rea[maxn], n, run , u , v;
pair<int, int> t[maxn];
char s[200002][2];

int main(){
   // freopen("input.in","r",stdin); 
   // freopen("output.out","w",stdout);
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%s", s[i]);
        if(s[i][0] == '?'){
            scanf("%d %d %d", &k[i], &t[i].fi, &b[i]);
        }
        else scanf("%d", &t[i].fi);
        t[i].se = i;
    }
    
    sort(t, t + n);
    a[t[0].se] = 1;
    for(int i = 1; i < n; i++){
        if(t[i].fi > t[i - 1].fi) a[t[i].se] = a[t[i - 1].se] + 1;
        else a[t[i].se] = a[t[i - 1].se];
        rea[a[t[i].se]] = t[i].fi;
    }
    run = 0;
    for(int i = 0; i < n; i++){
        if(s[i][0] == '?'){
            u = k[i] + get(a[i] - 1); 
            if(u > run) printf("0\n");
            else{
                v = kThElement(u);
                if(rea[v] > b[i]) printf("0\n");
                else printf("%d\n",rea[v]);
            }
        }
        else if(s[i][0] == '+'){
            insert(a[i]);
            update(a[i], 1);
            run++;
        }
        else{
            eraser(a[i]);
            update(a[i], -1);
            run--;
        }
    }
}

Download