Advertisement
AlejandroGY

Untitled

Feb 1st, 2018
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.36 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. constexpr int MAX = 100010;
  4.  
  5. int arr[MAX];
  6. int tree[4 * MAX], lazy[4 * MAX];
  7.  
  8. void build(int node, int ini, int fin)
  9. {
  10.     if (ini > fin) {
  11.         return;
  12.     }
  13.  
  14.     if (ini == fin) {
  15.         tree[node] = arr[ini];
  16.         return;
  17.     }
  18.     int mid = ini + (fin - ini) / 2;
  19.     build(2 * node, ini, mid);
  20.     build(2 * node + 1, mid + 1, fin);
  21.     tree[node] = std::min(tree[2 * node], tree[2 * node + 1]);
  22. }
  23.  
  24. void update(int node, int ini, int fin, int i, int j, int x, int value)
  25. {
  26.     if (ini > fin || ini > j || fin < i) {
  27.         return;
  28.     }
  29.  
  30.     if (lazy[node] != 0) {
  31.         tree[node] += lazy[node];
  32.         if (ini != fin) {
  33.             lazy[2 * node] += lazy[node];
  34.             lazy[2 * node + 1] += lazy[node];
  35.         }
  36.         lazy[node] = 0;
  37.     }
  38.  
  39.     if (tree[node] > x) {
  40.         tree[node] += value;
  41.         if (ini != fin) {
  42.             lazy[2 * node] += value;
  43.             lazy[2 * node + 1] += value;
  44.         }
  45.         return;
  46.     }
  47.  
  48.     if (ini == fin) {
  49.         return;
  50.     }
  51.  
  52.     int mid = ini + (fin - ini) / 2;
  53.     update(2 * node, ini, mid, i, j, x, value);
  54.     update(2 * node + 1, mid + 1, fin, i, j, x, value);
  55.     tree[node] = std::min(tree[2 * node], tree[2 * node + 1]);
  56. }
  57.  
  58. int query(int node, int ini, int fin, int i, int j)
  59. {
  60.     if (ini > fin || ini > j || fin < i) {
  61.         return INT_MAX;
  62.     }
  63.    
  64.     if (lazy[node] != 0) {
  65.         tree[node] += lazy[node];
  66.         if (ini != fin) {
  67.             lazy[2 * node] += lazy[node];
  68.             lazy[2 * node + 1] += lazy[node];
  69.         }
  70.         lazy[node] = 0;
  71.     }
  72.  
  73.     if (ini >= i && fin <= j) {
  74.         return tree[node];
  75.     }
  76.  
  77.     int mid = ini + (fin - ini) / 2;
  78.     int q1 = query(2 * node, ini, mid, i, j);
  79.     int q2 = query(2 * node + 1, mid + 1, fin, i, j);
  80.     return std::min(q1, q2);
  81. }
  82.  
  83. int main( )
  84. {
  85.     std::ios_base::sync_with_stdio(0);
  86.     std::cin.tie(0);
  87.     std::cout.tie(0);
  88.  
  89.     int n;
  90.     std::cin >> n;
  91.  
  92.     std::vector<std::pair<int,int>> v;
  93.     for (int i = 0; i < n; ++i) {
  94.         int test;
  95.         std::cin >> test;
  96.         v.push_back({ test, i + 1 });
  97.     }
  98.     std::sort(v.begin( ), v.end( ));
  99.  
  100.     for (int i = 0; i < n; ++i) {
  101.         arr[i] = v[i].first;
  102.     }
  103.  
  104.     build(1, 0, n - 1);
  105.     std::fill(lazy, lazy + (4 * MAX), 0);
  106.  
  107.     int q;
  108.     std::cin >> q;
  109.     while (q--) {
  110.         int x;
  111.         std::cin >> x;
  112.         update(1, 0, n - 1, 0, n - 1, x, -1);
  113.     }
  114.  
  115.     for (int i = 0; i < n; ++i) {
  116.         v[i].first = query(1, 0, n - 1, i, i);
  117.         std::swap(v[i].first, v[i].second);
  118.     }
  119.  
  120.     std::sort(v.begin( ), v.end( ));
  121.  
  122.     for (int i = 0; i < n; ++i) {
  123.         std::cout << v[i].second << " ";
  124.     }
  125. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement