Advertisement
Josif_tepe

Untitled

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