Advertisement
willy108

Untitled

Sep 18th, 2020
177
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.80 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <cstdlib>
  5. #include <ctime>
  6. #include <cmath>
  7. #include <cassert>
  8. #include <algorithm>
  9. #include <vector>
  10. #include <string>
  11. #include <map>
  12. #include <set>
  13. #include <sstream>
  14. #include <list>
  15. #include <queue>
  16. #include <stack>
  17. //#include <unordered_map>
  18. //#include <unordered_set>
  19. #include <functional>
  20.  
  21. #define max_v 210000
  22. #define ROOTN 500
  23. #define int_max 0x3f3f3f3f
  24. #define cont continue
  25. #define byte_max 0x3f
  26. #define pow_2(n) (1 << (n))
  27. //tree
  28. #define lsb(n) ((n)&(-(n)))
  29. #define LC(n) (((n) << 1) + 1)
  30. #define RC(n) (((n) << 1) + 2)
  31. #define LOG2(n) ((int)(ceil(log2((n)))))
  32. using namespace std;
  33.  
  34. void setIO(const string& file_name){
  35.     freopen((file_name+".in").c_str(), "r", stdin);
  36.     freopen((file_name+".out").c_str(), "w+", stdout);
  37. }
  38.  
  39. int arr[max_v], n, q;
  40. int maxi[ROOTN];
  41. int hotels[ROOTN][ROOTN];
  42.  
  43. int Q(int k){
  44.   int ind = -1;
  45.   for(int i = 0; i<=n/ROOTN; i++){
  46.     if(maxi[i] >= ind){ ind = i; break; }
  47.   }
  48.  
  49.   if(ind == -1) return 0;
  50.  
  51.   for(int i = 0; i<ROOTN; i++){
  52.     if(hotels[ind][i] >= k) return ind * ROOTN + i + 1;
  53.   }
  54.   return 0; //should not happen but a return value is there for safety
  55. }
  56.  
  57. void U(int k, int val){
  58.   hotels[k/ROOTN][k % ROOTN] -= val;
  59.   maxi[k/ROOTN] = 0;
  60.   for(int i = 0; i<ROOTN; i++) maxi[k/ROOTN] = max(maxi[k/ROOTN], hotels[k/ROOTN][i]);
  61. }
  62.  
  63. void precomp(){
  64.   for(int i = 0; i<n; i++){
  65.     hotels[i/ROOTN][i % ROOTN] = arr[i];
  66.     maxi[i/ROOTN] = max(maxi[i/ROOTN], arr[i]);
  67.   }
  68. }
  69.  
  70.  
  71.  
  72. int main(){ //first time using sqrt decomp
  73.     scanf("%d%d", &n, &q);
  74.   for(int i = 0; i<n; i++){
  75.     scanf("%d", &arr[i]);
  76.   }
  77.   precomp();
  78.   for(;q--;){
  79.     int a, res;
  80.     scanf("%d", &a);
  81.     res = Q(a);
  82.     printf("%d ", res);
  83.     if(res) U(res - 1, a);
  84.   }
  85.     return 0;
  86. }
  87.  
  88.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement