Advertisement
Josif_tepe

Untitled

Apr 4th, 2023
1,007
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.01 KB | None | 0 0
  1. #include <iostream>
  2. #include <set>
  3. #include <vector>
  4. #include <map>
  5. //#include <bits/stdc++.h>
  6.  
  7. using namespace std;
  8. typedef long long ll;
  9. const int maxn = 2e5 + 10;
  10.  
  11. ll segment_tree[3 * maxn];
  12. void build_tree(int L, int R, int position) {
  13.     if(L == R) {
  14.         segment_tree[position] = 0;
  15.     }
  16.     else {
  17.         int middle = (L + R) / 2;
  18.         build_tree(L, middle, 2 * position);
  19.         build_tree(middle + 1, R, 2 * position + 1);
  20.         segment_tree[position] = segment_tree[2 * position] + segment_tree[2 * position + 1];
  21.     }
  22. }
  23. // L R i L R j L R
  24. ll query(int L, int R, int position, int i, int j) {
  25.     if(i <= L and R <= j) {
  26.         return segment_tree[position];
  27.     }
  28.     if(R < i or j < L) {
  29.         return 0;
  30.     }
  31.     int middle = (L + R) / 2;
  32.     return query(L, middle, 2 * position, i, j) + query(middle + 1, R, 2 * position + 1, i, j);
  33. }
  34. void update(int L, int R, int position, int idx, ll new_val) {
  35.     if(L == R) {
  36.         segment_tree[position] += new_val;
  37.         return;
  38.     }
  39.     int middle = (L + R) / 2;
  40.     if(idx <= middle) {
  41.         update(L, middle, 2 * position, idx, new_val);
  42.     }
  43.     else {
  44.         update(middle + 1, R, 2 * position + 1, idx, new_val);
  45.     }
  46.     segment_tree[position] = segment_tree[2 * position] + segment_tree[2 * position + 1];
  47. }
  48. struct node {
  49.     int v, k, idx;
  50.     node () {}
  51.     node(int _idx, int _v, int _k) {
  52.         idx = _idx;
  53.         v = _v;
  54.         k = _k;
  55.     }
  56.     bool operator < (const node &tmp) const {
  57.         return v < tmp.v;
  58.     }
  59. };
  60. int main() {
  61.     ios_base::sync_with_stdio(false);
  62.     int n;
  63.     cin >> n;
  64.     vector<pair<int, int> > original_values;
  65.     vector<node> to_be_compressed;
  66.     for(int i = 0; i < n; i++) {
  67.         int a, b;
  68.         cin >> a >> b;
  69.         original_values.push_back(make_pair(a, b));
  70.         to_be_compressed.push_back(node(i, a, b));
  71.     }
  72.     sort(to_be_compressed.begin(), to_be_compressed.end());
  73.     map<int, int> mapa;
  74.     int c = 0;
  75.     for(int i = 0; i < n; i++) {
  76.         if(mapa.find(to_be_compressed[i].v) == mapa.end()) {
  77.             mapa[to_be_compressed[i].v] = c;
  78.             c++;
  79.         }
  80.     }
  81.     vector<pair<int, int> > compressed_values(n);
  82.     map<int, int> orig_value;
  83.     for(int i = 0; i < n; i++) {
  84.         compressed_values[to_be_compressed[i].idx] = make_pair(mapa[to_be_compressed[i].v],to_be_compressed[i].k);
  85.         orig_value[mapa[to_be_compressed[i].v]] = to_be_compressed[i].v;
  86.     }
  87.     build_tree(0, n + 1, 1);
  88.     ll sum = 0;
  89.     for(int i = 0; i < n; i++) {
  90.         int v = compressed_values[i].first, k = compressed_values[i].second;
  91.         sum += k;
  92.         update(0, n, 1, v, k);
  93.         int L = 0, R = n;
  94.         while(L < R) {
  95.             int middle = L + (R - L) / 2;
  96.             if(query(0, n, 1, 0, middle) >= (sum + 1) / 2) {
  97.                 R = middle;
  98.             }
  99.             else {
  100.                 L = middle + 1;
  101.             }
  102.         }
  103.         cout << orig_value[L] << "\n";
  104.     }
  105.     return 0;
  106. }
  107.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement