Untitled

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;

using namespace std;
const int maxn = 2e5 + 10;
ll segment_tree[3 * maxn];
void build(int L, int R, int pos) {
    if(L == R) {
        segment_tree[pos] = 0;
        return;
    }
    int mid = (L + R) >> 1;
    build(L, mid, 2 * pos);
    build(mid + 1, R, 2 * pos + 1);
    segment_tree[pos] = segment_tree[2 * pos] + segment_tree[2 * pos + 1];
}
// L R i L R j L R
ll query(int L, int R, int pos, int idx) {
    if(0 <= L and R <= idx) {
        return segment_tree[pos];
    }
    if(R < 0 or idx < L) {
        return 0;
    }
    int mid = (L + R) >> 1;
    return query(L, mid, 2 * pos, idx) + query(mid + 1, R, 2 * pos + 1, idx);
}
void update(int L, int R, int pos, int idx, int new_val) {
    if(L == R) {
        segment_tree[pos] += new_val;
        return;
    }
    int mid = (L + R) >> 1;
    if(idx <= mid) {
        update(L, mid, 2 * pos, idx, new_val);
    }
    else {
        update(mid + 1, R, 2 * pos + 1, idx, new_val);
    }
    segment_tree[pos] = segment_tree[2 * pos] + segment_tree[2 * pos + 1];
}
struct node {
    int idx, v, k;
    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 values_to_be_compressed;
    vector > original_values;
    for(int i = 0; i < n; i++) {
        int v, k;
        cin >> v >> k;
        values_to_be_compressed.push_back(node(i, v, k));
        original_values.push_back(make_pair(v, k));
    }
    sort(values_to_be_compressed.begin(), values_to_be_compressed.end());
    int cords = 0;
    map mapa;
    for(int i = 0; i < n; i++) {
        if(mapa.find(values_to_be_compressed[i].v) == mapa.end()) {
            mapa[values_to_be_compressed[i].v] = cords;
            cords++;
        }
    }
    vector > compressed_value(n);
    map reverse_compression;
    for(int i = 0; i < n; i++) {
        compressed_value[values_to_be_compressed[i].idx] = make_pair(mapa[values_to_be_compressed[i].v], values_to_be_compressed[i].k);
        
        reverse_compression[mapa[values_to_be_compressed[i].v]] = values_to_be_compressed[i].v;
    }
    ll sum =0 ;
    build(0, n, 1);
    for(int i = 0; i < n; i++) {
        update(0, n, 1, compressed_value[i].first, compressed_value[i].second);
        sum += compressed_value[i].second;
        int L = 0, R = n;
        while(L < R) {
            int mid = L + (R - L) / 2;
            if(query(0, n, 1, mid) >= (sum + 1) / 2) {
                R = mid;
            }
            else {
                L = mid + 1;
            }
        }
        cout << reverse_compression[L] << "\n";
    }
    return 0;
}

/*
 7 5
 10 4
 10 8
 15 2
 17 5
 **/