Submission #1359091

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

template<class V, int ME> class BIT {
public:
    V bit[1<<ME];
    V total(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
    void update(int e, V val) {e++; while(e<=1<<ME) bit[e-1]+=val,e+=e&-e;}
};

BIT<int, 18> bit;
bool val[1<<18] = {};

ll binary_search(ll X, ll i, ll j){
    if(i+1==j) return j;
    ll mid = (i+j)/2;
    if(bit.total(mid)>=X){
        return binary_search(X, i, mid);
    }else{
        return binary_search(X, mid, j);
    }
}

int main(){
    int Q;
    cin >> Q;
    REP(i, Q){
        ll T, X;
        cin >> T >> X;
        if(T==1){
            bit.update(X, 1);
            val[X] = true;
        }
        if(T==2){
            ll Y = binary_search(X, 0, 1<<18);
            cout << Y << endl;
            bit.update(Y, -1);
            val[Y] = 0;
        }
    }
    return 0;
}

Submission Info

Judge Result