Advertisement
Fshl0

dwdwd

Apr 23rd, 2022
979
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.13 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define F first
  3. #define S second
  4. #define pb push_back
  5. #define mp make_pair
  6.  
  7. using namespace std;
  8. typedef long long ll;
  9. typedef pair <ll, ll> pii;
  10.  
  11. #include <ext/pb_ds/assoc_container.hpp>
  12. #include <ext/pb_ds/tree_policy.hpp>
  13. using namespace __gnu_pbds;
  14.  
  15. #define ordered_set tree<pair<ll,int>, null_type,less<pair<ll,int>>, rb_tree_tag,tree_order_statistics_node_update>
  16.  
  17. const int INF = 1e7;
  18. const ll llINF = 1e17;
  19. const int mxN = 2e5 + 9;
  20. const int mxM = 1e5 + 9;
  21. const int MOD = 1e9 + 7;
  22. const double pi = acos (-1);
  23.  
  24. void setIO (string s) {
  25.     freopen ((s + ".in").c_str(), "r", stdin);
  26.     freopen ((s + ".out").c_str(), "w", stdout);
  27.    
  28.     return;
  29. }
  30.  
  31. int segTree[4 * mxN], m;
  32.  
  33. void buildTree (int v, int l, int r) {
  34.     if (l == r) {
  35.         segTree[v] = m;
  36.         return;
  37.     }
  38.    
  39.     int mid = (l + r) >> 1;
  40.     buildTree (2 * v, l, mid);
  41.     buildTree (2 * v + 1, mid + 1, r);
  42.    
  43.     segTree[v] = max (segTree[2 * v], segTree[2 * v + 1]);
  44.     return;
  45. }
  46.  
  47. int getQuery (int v, int l, int r, int val) {
  48.     if (l == r)
  49.         return l;
  50.        
  51.     int mid = (l + r) >> 1;
  52.     if (segTree[2 * v] >= val) {
  53.         return getQuery (2 * v, l, mid, val);
  54.     } else if (segTree[2 * v + 1] >= val) {
  55.         return getQuery (2 * v + 1, mid + 1, r, val);
  56.     } else return -1;
  57. }
  58.  
  59. void updateTree (int v, int l, int r, int idx, int val) {
  60.     if (l == r) {
  61.         segTree[v] -= val;
  62.         return;
  63.     }  
  64.    
  65.     int mid = (l + r) >> 1;
  66.     if (idx <= mid) {
  67.         updateTree (2 * v, l, mid, idx, val);
  68.     } else updateTree (2 * v + 1, mid + 1, r, idx, val);
  69.    
  70.     segTree[v] = max (segTree[2 * v], segTree[2 * v + 1]);
  71. }
  72.  
  73. void solve () {
  74.     int n;
  75.     cin >> n >> m;
  76.        
  77.     int Q;
  78.     cin >> Q;
  79.    
  80.     n = min (n, Q);
  81.     buildTree (1, 1, n);
  82.    
  83.     while (Q--) {
  84.         int x;
  85.         cin >> x;
  86.        
  87.         int res = getQuery (1, 1, n, x);
  88.         if (res == -1) {
  89.             cout << -1 << "\n";
  90.         } else {
  91.             cout << res << "\n";
  92.             updateTree (1, 1, n, res, x);
  93.         }
  94.     }
  95.    
  96.     return;
  97. }
  98.  
  99. int main () {
  100.     int t = 1;
  101.     //cin >> t;
  102.    
  103.     ios_base::sync_with_stdio (0);
  104.     cin.tie (0);
  105.    
  106.     setIO ("billboard");
  107.     //preCalc ();
  108.     while (t--) {
  109.         //initialize common variables
  110.        
  111.        
  112.         //go solve
  113.         solve ();
  114.     }
  115.        
  116.     return 0;
  117. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement