Advertisement
Josif_tepe

Untitled

Jun 6th, 2024
319
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.77 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int maxn = 1e5 + 10;
  4. const int INF = 1e8;
  5. int a[maxn];
  6. int n;
  7. int segment_tree[3 * maxn];
  8. void build(int L, int R, int pos) {
  9.   if(L == R) {
  10.     segment_tree[pos] = 1;
  11.   }
  12.   else {
  13.     int middle = (L + R) / 2;
  14.     build(L, middle, 2 * pos);
  15.     build(middle + 1, R, 2 * pos + 1);
  16.     segment_tree[pos] = segment_tree[2 * pos] + segment_tree[2 * pos + 1];
  17.   }
  18.  
  19. }
  20. void update(int L, int R, int pos, int idx) {
  21.   if(L == R) {
  22.     segment_tree[pos] = 0;
  23.     return;
  24.   }
  25.   int middle = (L + R) / 2;
  26.   if(idx <= middle) {
  27.     update(L, middle, 2 * pos, idx);
  28.   }
  29.   else {
  30.     update(middle + 1, R, 2 * pos + 1, idx);
  31.   }
  32.   segment_tree[pos] = segment_tree[2 * pos] + segment_tree[2 * pos + 1];
  33. }
  34. int query(int L, int R, int pos, int x) {
  35.     if(L == R) {
  36.       return L;
  37.     }
  38.     int middle = (L + R) / 2;
  39.     if(segment_tree[2 * pos] >= x) {
  40.       return query(L, middle, 2 * pos, x);
  41.     }
  42.     else {
  43.       return query(middle + 1, R, 2 * pos + 1, x - segment_tree[2 * pos]);
  44.     }
  45. }
  46. int main()
  47. {
  48.     ios_base::sync_with_stdio(false);
  49.     cin >> n;
  50.     for(int i = 0; i < n; i++) {
  51.       cin >> a[i];
  52.     }
  53.     sort(a, a + n);
  54.     build(0, n - 1, 1);
  55.     vector<int> q(n);
  56.     for(int i = 0; i < n; i++) {
  57.         cin >> q[i];
  58.         q[i]++;
  59.       }
  60.       vector<int> res(n);
  61.       for(int i = n - 1; i >= 0; i--) {
  62.         int idx = query(0, n - 1, 1, q[i]);
  63.        
  64.         res[i] = a[idx];
  65.        
  66.        
  67.         update(0, n - 1, 1, idx);
  68.    
  69.       }
  70.       for(int i = 0; i < n; i++) {
  71.         cout << res[i] << " ";
  72.       }
  73.       return 0;
  74. }
  75. //    134  167  
  76. // 0 1 0 0 3 2 6 7 4 6 9 4
  77.  
  78. // 134 167 120 119 156 120 167 182 155 163 172 145
  79.  
  80. // 1 1 1 1 0 1 1 1 1 1 0 1  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement