Advertisement
Josif_tepe

Untitled

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