Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <map>
- #include <vector>
- #include <fstream>
- #include <algorithm>
- 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<node> values_to_be_compressed;
- vector<pair<int, int> > 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<int, int> 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<pair<int, int> > compressed_value(n);
- map<int, int> 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
- **/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement