Guest User

CSES - Hotel Queries - O(log n)

a guest
Jan 15th, 2021
175
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define f first
  5. #define s second
  6. #define pb push_back
  7. #define rep(i, begin, end)                                                     \
  8.   for (__typeof(end) i = (begin) - ((begin) > (end));                          \
  9.        i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
  10. #define db(x) cout << '>' << #x << ':' << x << endl;
  11. #define sz(x) ((int)(x).size())
  12. #define newl cout << "\n"
  13.  
  14. #define ll long long int
  15. #define vi vector<int>
  16. #define vll vector<long long>
  17. #define vvll vector<vll>
  18. #define pll pair<long long, long long>
  19.  
  20. #define fast_io()                                                              \
  21.   ios_base::sync_with_stdio(false);                                            \
  22.   cin.tie(NULL);                                                               \
  23.   cout.tie(NULL);
  24.  
  25. const int mxN = 2e5 + 5;
  26. const int mxM = 2e5 + 7;
  27. const int lg = 22;
  28. ll N = 0;
  29.  
  30. template <class T> struct Seg {
  31.   const T ID = 0;
  32.   // comb(ID,b) = b
  33.   T comb(T a, T b) { return max(a, b); }
  34.   vector<int> roots;
  35.   int n;
  36.   vector<T> seg;
  37.   void init(int _n) {
  38.     n = _n;
  39.     seg.assign(2*n, ID);
  40.   }
  41.  
  42.   void init_roots(){
  43.     vector<int> roots_r;
  44.     for(auto l = n, r = n<<1; l < r; l >>= 1, r >>= 1){
  45.       if(l & 1) roots.push_back(l++);
  46.       if(r & 1) roots_r.push_back(--r);
  47.     }
  48.     roots.insert(roots.end(), roots_r.rbegin(), roots_r.rend());
  49.   }
  50.  
  51.   void pull(int p) { seg[p] = comb(seg[p<<1], seg[p<<1^1]); }
  52.  
  53.   void upd(int p, T val) { // set val at position p
  54.     seg[p += n] = val;
  55.     for (p = p>>1; p; p = p>>1) pull(p);
  56.   }
  57.  
  58.   T qry(int l, int r) { // on interval [l, r]
  59.     T ra = ID, rb = ID;
  60.     for (l += n, r += n + 1; l < r; l = l>>1, r = r>>1) {
  61.       if (l & 1) ra = comb(ra, seg[l++]);
  62.       if (r & 1) rb = comb(seg[--r], rb);
  63.     }
  64.     return comb(ra, rb);
  65.   }
  66.  
  67.   // log(n) * log(n)
  68.   ll findfirst_1(ll rn) {
  69.     int l = -1, r = n-1;
  70.     while(r-l > 1) {
  71.       auto mid = (r+l)>>1;
  72.       if(qry(0, mid) < rn) l = mid;
  73.       else r = mid;
  74.     }
  75.     if(qry(r, r) >= rn) return r;
  76.     return -1;
  77.   }
  78.  
  79.   // log(n); need biggest power of 2 in iterative segment tree, greater than equal to n;
  80.   ll findfirst_2(ll x) {
  81.     // return any value from [0, n-1] if present; else return -1;
  82.     ll ans = -1;
  83.     ll i = 1;
  84.     while(i < n && seg[i] >= x) {
  85.       if(seg[i<<1] >= x) i = i<<1;
  86.       else if(seg[i<<1^1] >= x) i = i<<1^1;
  87.       else return -1;
  88.     }
  89.     if(seg[i] >= x) return i-n;
  90.     return -1;
  91.   }
  92.  
  93.   // log(n), does not need n to be power of 2
  94.   ll findfirst_3(ll x) {
  95.     if(qry(0, n-1) < x) return -1;
  96.     ll j = 0; // iterate every root;
  97.     while(j < seg.size() && seg[roots[j]] < x) {
  98.       j++;
  99.     }
  100.     // found the first root, containing el>=x;
  101.     ll i = roots[j];
  102.     while(i < n && seg[i] >= x) {
  103.       if(seg[i<<1] >= x) i = i<<1;
  104.       else i = i<<1^1;
  105.     }
  106.     return i-n;
  107.   }
  108. };
  109.  
  110. ll tc, n, m, k;
  111.  
  112. Seg<ll> st;
  113.  
  114.  
  115. int main() {
  116.   fast_io();
  117. #ifndef ONLINE_JUDGE
  118.   freopen("../input.txt", "r", stdin);
  119.   freopen("../output.txt", "w", stdout);
  120. #endif
  121.  
  122.   cin>>n>>m;
  123.  
  124. //  for(int i = 0; N = 1<<i, 1<<i < n; i++);
  125. //  st.init(N);
  126.  
  127.   st.init(n);
  128.   st.init_roots();
  129.  
  130.   rep(i, 0, n) {
  131.     ll x; cin>>x;
  132.     st.upd(i, x);
  133.   }
  134.  
  135.   rep(i, 0, m) {
  136.     ll rn; cin>>rn;
  137.     ll ans = 0;
  138.     ans = st.findfirst_3(rn);
  139.     if(ans != -1) {
  140.       cout<<ans+1<<" ";
  141.       st.upd(ans, st.qry(ans, ans)-rn);
  142.     } else {
  143.       cout<<0<<" ";
  144.     }
  145.   }
  146.  
  147.   return 0;
  148. }
RAW Paste Data