fork download
copy 
  1. // i wants to take ioi
  2. //binhtinhtutinkhongcaycunhungmotkhikhongcontutinnualatuyetvong
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. #define int long long
  8. #define nn "\n"
  9. #define pi pair<int, int>
  10. #define ti tuple<int, int, int>
  11. #define fi first
  12. #define se second
  13. #define lb lower_bound
  14. #define ub upper_bound
  15. #define eb emplace_back
  16. #define pb push_back
  17. #define TASK " "
  18.  
  19. #define ms(a, x) memset(a, x, sizeof(a))
  20. #define all(a) a.begin(), a.end()
  21. #define All(a, n) a + 1, a + 1 + n
  22.  
  23. #define LOG 19
  24.  
  25. const int INF = 1e18;
  26. const int N = 1e5 + 5;
  27.  
  28. int n, m;
  29. int a[N];
  30. int st[4 * N], lazy[4 * N];
  31.  
  32. void build(int id, int l, int r){
  33.     if(l == r){
  34.         st[id] = a[l];
  35.         return;
  36.     }
  37.  
  38.     int mid = (l + r) >> 1;
  39.  
  40.     build(id * 2, l, mid);
  41.     build(id * 2 + 1, mid + 1, r);
  42.  
  43.     st[id] = max(st[id * 2], st[id * 2 + 1]);
  44. }
  45.  
  46. void fix(int id, int val){
  47.     st[id] += val;
  48.     lazy[id] += val;
  49. }
  50.  
  51. void down(int id){
  52.     if(lazy[id] == 0) return;
  53.  
  54.     fix(id * 2, lazy[id]);
  55.     fix(id * 2 + 1, lazy[id]);
  56.  
  57.     lazy[id] = 0;
  58. }
  59.  
  60. void update(int id, int l, int r, int u, int v, int val){
  61.     if(u > r || v < l) return;
  62.  
  63.     if(u <= l && r <= v){
  64.         fix(id, val);
  65.         return;
  66.     }
  67.  
  68.     down(id);
  69.  
  70.     int mid = (l + r) >> 1;
  71.  
  72.     update(id * 2, l, mid, u, v, val);
  73.     update(id * 2 + 1, mid + 1, r, u, v, val);
  74.  
  75.     st[id] = max(st[id * 2], st[id * 2 + 1]);
  76. }
  77.  
  78. int get(int id, int l, int r, int x){
  79.     if(st[id] < x) return n + 1;
  80.  
  81.     if(l == r) return l;
  82.  
  83.     down(id);
  84.  
  85.     int mid = (l + r) >> 1;
  86.  
  87.     int res = get(id * 2, l, mid, x);
  88.  
  89.     if(res != n + 1) return res;
  90.  
  91.     return get(id * 2 + 1, mid + 1, r, x);
  92. }
  93.  
  94. void solve(){
  95.     cin >> n;
  96.  
  97.     for(int i = 1; i <= n; i++){
  98.         cin >> a[i];
  99.     }
  100.  
  101.     sort(a + 1, a + n + 1);
  102.  
  103.     build(1, 1, n);
  104.  
  105.     cin >> m;
  106.  
  107.     for(int i = 1; i <= m; i++){
  108.         int t;
  109.         cin >> t;
  110.  
  111.         int p = get(1, 1, n, t);
  112.  
  113.         if(p == n + 1){
  114.             cout << 0 << " ";
  115.         }
  116.         else{
  117.             cout << n - p + 1 << " ";
  118.             update(1, 1, n, p, n, -1);
  119.         }
  120.     }
  121.  
  122.     cout << nn;
  123. }
  124.  
  125. signed main(){
  126.     ios_base::sync_with_stdio(0);
  127.     cin.tie(0);
  128.     cout.tie(0);
  129.  
  130.     solve();
  131.  
  132.     return (0 ^ 0);
  133. }
Success #stdin #stdout 0.01s 5800KB
comments (?)
stdin
copy 
3
3 1 1
2
1 2
stdout
copy 
3 1
https://ideone.com/GZO0bJ
language:
C++14 (gcc 8.3)
created:
19 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!