Advertisement
MinhNGUYEN2k4

Untitled

Sep 10th, 2021
1,132
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.43 KB | None | 0 0
  1. //Nguyen Huu Hoang Minh
  2. #include <bits/stdc++.h>
  3. #define sz(x) int(x.size())
  4. #define all(x) x.begin(),x.end()
  5. #define reset(x) memset(x, 0,sizeof(x))
  6. #define pb push_back
  7. #define mp make_pair
  8. #define fi first
  9. #define se second
  10. #define N 300005
  11. #define remain(x) if (x > MOD) x -= MOD
  12. #define ii pair<int, int>
  13. #define iiii pair< ii , ii >
  14. #define viiii vector< iiii >
  15. #define vi vector<int>
  16. #define vii vector< ii >
  17. #define bit(x, i) (((x) >> (i)) & 1)
  18. #define Task "test"
  19. #define int long long
  20.  
  21. using namespace std;
  22.  
  23. typedef long double ld;
  24. const int inf = 1e10;
  25. const int minf = -1e10;
  26.  
  27. int n, m;
  28. int bl[N], gr[N], wh[N];
  29. int h[3000005];
  30. int b[3000005];
  31. int c[3000005];
  32.  
  33. void readfile()
  34. {
  35.     ios_base::sync_with_stdio(false);
  36.     cin.tie(0);cout.tie(0);
  37.     if (fopen(Task".inp","r"))
  38.     {
  39.         freopen(Task".inp","r",stdin);
  40.         //freopen(Task".out","w",stdout);
  41.     }
  42.     cin >> n;
  43.     for(int i=1; i<=n; i++) cin >> bl[i];
  44.     for(int i=1; i<=n; i++) cin >> gr[i];
  45.     for(int i=1; i<=n; i++) cin >> wh[i];
  46.     for(int i=1; i<=n; i++){
  47.         h[bl[i]]++;
  48.         h[bl[i]+gr[i]]+=2;
  49.         h[bl[i]]-=2;
  50.         h[bl[i]+gr[i]+wh[i]]+=5;
  51.         h[bl[i]+gr[i]]-=5;
  52.     }
  53.     for(int i=3000000; i>=1; i--) h[i] += h[i+1];
  54. }
  55.  
  56. int tr[3000005*4];
  57.  
  58. void build(int id, int l, int r){
  59.     if (r==l){
  60.         tr[id] = 1;
  61.         return;
  62.     }
  63.     int mid = (l+r)/2;
  64.     build(id*2,l,mid);
  65.     build(id*2+1,mid+1,r);
  66.     tr[id] = tr[id*2] + tr[id*2+1];
  67. }
  68.  
  69. void up(int id, int l, int r, int u){
  70.     if (r < u || u < l) return;
  71.     if (r==l && l==u){
  72.         tr[id] = 0;
  73.         return;
  74.     }
  75.     int mid = (l+r)/2;
  76.     up(id*2,l,mid,u);
  77.     up(id*2+1,mid+1,r,u);
  78.     tr[id] = tr[id*2] + tr[id*2+1];
  79. }
  80.  
  81. int get(int id, int l, int r, int val){
  82.     if (l > r) return -1;
  83.     if (tr[id] < val) return -1;
  84.     if (l==r) return l;
  85.     int mid = (l+r)/2;
  86.     if (tr[id*2] < val){
  87.         val -= tr[id*2];
  88.         return get(id*2+1,mid+1,r,val);
  89.     }
  90.     return get(id*2,l,mid,val);
  91. }
  92.  
  93. void proc()
  94. {
  95.     int q; cin >> q;
  96.     int ans = 0;
  97.     int Pmax = 3000000;
  98.     build(1,1,Pmax);
  99.     while (q--){
  100.         int hi; cin >> hi;
  101.         int p = get(1,1,Pmax,hi);
  102.         if (p==-1){
  103.             cout << 0 << '\n';
  104.         }
  105.         else{
  106.             cout << h[p] << '\n';
  107.             up(1,1,Pmax,p);
  108.         }
  109.     }
  110. }
  111.  
  112. signed main()
  113. {
  114.     readfile();
  115.     proc();
  116.     return 0;
  117. }
  118.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement