Submission #1513263

---

Source Code Expand

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

// 0-indexed
template <typename T>
class fenwick_tree {
public:
    fenwick_tree(int n) : n(n), dat(n, 0) {}

    void add(int i, T value) {
        for(; i<n; i |= i + 1) {
            dat[i] += value;
        }
    }

    T sum(int i) const {
        T res = 0;
        for(; i>=0; i = (i & (i+1)) - 1) {
            res += dat[i];
        }
        return res;
    }
    // [l, r)
    T sum(int l, int r) const {
        return sum(r-1) - sum(l-1);
    }

private:
    const int n;
    std::vector<T> dat;
};


int main() {
    int Q;
    cin >> Q;
    fenwick_tree<int> bit(200001);
    while(Q--) {
        int T, X;
        cin >> T >> X;
        if(T == 1) {
            bit.add(X, 1);
        } else {
            int l = -1, r = 200000;
            while(r - l > 1) {
                int m = (l + r) / 2;
                if(bit.sum(m) >= X) {
                    r = m;
                } else {
                    l = m;
                }
            }
            cout << r << endl;
            bit.add(r, -1);
        }
    }
}

Submission Info

Judge Result