Untitled

#include 
#include 
#include 
#include 
//#include 

using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;

ll segment_tree[3 * maxn];
void build_tree(int L, int R, int position) {
    if(L == R) {
        segment_tree[position] = 0;
    }
    else {
        int middle = (L + R) / 2;
        build_tree(L, middle, 2 * position);
        build_tree(middle + 1, R, 2 * position + 1);
        segment_tree[position] = segment_tree[2 * position] + segment_tree[2 * position + 1];
    }
}
// L R i L R j L R
ll query(int L, int R, int position, int i, int j) {
    if(i <= L and R <= j) {
        return segment_tree[position];
    }
    if(R < i or j < L) {
        return 0;
    }
    int middle = (L + R) / 2;
    return query(L, middle, 2 * position, i, j) + query(middle + 1, R, 2 * position + 1, i, j);
}
void update(int L, int R, int position, int idx, ll new_val) {
    if(L == R) {
        segment_tree[position] += new_val;
        return;
    }
    int middle = (L + R) / 2;
    if(idx <= middle) {
        update(L, middle, 2 * position, idx, new_val);
    }
    else {
        update(middle + 1, R, 2 * position + 1, idx, new_val);
    }
    segment_tree[position] = segment_tree[2 * position] + segment_tree[2 * position + 1];
}
struct node {
    int v, k, idx;
    node () {}
    node(int _idx, int _v, int _k) {
        idx = _idx;
        v = _v;
        k = _k;
    }
    bool operator < (const node &tmp) const {
        return v < tmp.v;
    }
};
int main() {
    ios_base::sync_with_stdio(false);
    int n;
    cin >> n;
    vector > original_values;
    vector to_be_compressed;
    for(int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        original_values.push_back(make_pair(a, b));
        to_be_compressed.push_back(node(i, a, b));
    }
    sort(to_be_compressed.begin(), to_be_compressed.end());
    map mapa;
    int c = 0;
    for(int i = 0; i < n; i++) {
        if(mapa.find(to_be_compressed[i].v) == mapa.end()) {
            mapa[to_be_compressed[i].v] = c;
            c++;
        }
    }
    vector > compressed_values(n);
    map orig_value;
    for(int i = 0; i < n; i++) {
        compressed_values[to_be_compressed[i].idx] = make_pair(mapa[to_be_compressed[i].v],to_be_compressed[i].k);
        orig_value[mapa[to_be_compressed[i].v]] = to_be_compressed[i].v;
    }
    build_tree(0, n + 1, 1);
    ll sum = 0;
    for(int i = 0; i < n; i++) {
        int v = compressed_values[i].first, k = compressed_values[i].second;
        sum += k;
        update(0, n, 1, v, k);
        int L = 0, R = n;
        while(L < R) {
            int middle = L + (R - L) / 2;
            if(query(0, n, 1, 0, middle) >= (sum + 1) / 2) {
                R = middle;
            }
            else {
                L = middle + 1;
            }
        }
        cout << orig_value[L] << "\n";
    }
    return 0;
}