Josif_tepe

Untitled

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