Josif_tepe

Untitled

Nov 9th, 2025
119
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.86 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. typedef long long ll;
  5. const int maxn = 1000005;
  6.  
  7. int segment_tree[3 * maxn];
  8.  
  9. int merge_nodes(int A, int B) {
  10.     return A + B;
  11. }
  12. void build_tree(int L, int R, int node) {
  13.     if(L == R) {
  14.         segment_tree[node] = 1;
  15.         return;
  16.     }
  17.    
  18.     int middle = (L + R) / 2;
  19.     build_tree(L, middle, 2 * node);
  20.     build_tree(middle + 1, R, 2 * node + 1);
  21.     segment_tree[node] = merge_nodes(segment_tree[2 * node], segment_tree[2 * node + 1]);
  22. }
  23.  
  24. int query(int x, int L, int R, int node) {
  25.     if(L == R) {
  26.         return L;
  27.     }
  28.    
  29.     int middle = (L + R) / 2;
  30.     if(segment_tree[2 * node] >= x) {
  31.         return query(x, L, middle, 2 * node);
  32.     }
  33.     else {
  34.         return query(x - segment_tree[2 * node], middle + 1, R, 2 * node + 1);
  35.     }
  36.    
  37. }
  38. void update(int idx, int L, int R, int node) {
  39.     if(L == R) {
  40.         segment_tree[node] = 0;
  41.         return;
  42.     }
  43.     int middle = (L + R) / 2;
  44.    
  45.     if(idx <= middle) {
  46.         update(idx, L, middle, 2 * node);
  47.     }
  48.     else {
  49.         update(idx, middle + 1, R, 2 * node + 1);
  50.     }
  51.    
  52.     segment_tree[node] = merge_nodes(segment_tree[2 * node], segment_tree[2 * node + 1]);
  53.    
  54. }
  55. int main() {
  56.     ios_base::sync_with_stdio(false);
  57.     int n;
  58.     cin >> n;
  59.    
  60.     vector<int> v(n);
  61.     for(int i = 0; i < n; i++) {
  62.         cin >> v[i];
  63.     }
  64.    
  65.     sort(v.begin(), v.end());
  66.     build_tree(0, n - 1, 1);
  67.     vector<int> q(n);
  68.     for(int i = 0; i < n; i++) {
  69.         cin >> q[i];
  70.         q[i]++;
  71.     }
  72.    
  73.     vector<int> res(n);
  74.     for(int i= n - 1; i >= 0;i --) {
  75.         int idx = query(q[i], 0, n - 1, 1);
  76.         res[i] = v[idx];
  77.        
  78.         update(idx, 0, n - 1, 1);
  79.     }
  80.    
  81.     for(int i = 0; i < n; i++) {
  82.         cout << res[i] << " ";
  83.     }
  84.     return 0;
  85. }
  86.  
Advertisement
Add Comment
Please, Sign In to add comment