fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ull unsigned long long
  4. #define ll long long
  5. #define fast ios::sync_with_stdio(false); cin.tie(nullptr);
  6.  
  7. struct Node {
  8.     ll key;
  9.     int pr;
  10.     int sz;
  11.     ll lz;
  12.     Node *l, *r;
  13.     Node(ll _key, int _pr): key(_key), pr(_pr), sz(1), lz(0), l(nullptr), r(nullptr) {}
  14. };
  15.  
  16. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  17.  
  18. int getsz(Node* t) {
  19.     return t ? t->sz : 0;
  20. }
  21.  
  22. void upd(Node* t) {
  23.     if (t) {
  24.         t->sz = 1 + getsz(t->l) + getsz(t->r);
  25.     }
  26. }
  27.  
  28. void apply_lazy(Node* t, ll v) {
  29.     if (!t) return;
  30.     t->key += v;
  31.     t->lz += v;
  32. }
  33.  
  34. void push(Node* t) {
  35.     if (t && t->lz != 0) {
  36.         apply_lazy(t->l, t->lz);
  37.         apply_lazy(t->r, t->lz);
  38.         t->lz = 0;
  39.     }
  40. }
  41.  
  42. pair<Node*, Node*> split(Node* t, ll key) {
  43.     if (!t) return {nullptr, nullptr};
  44.     push(t);
  45.     if (t->key < key) {
  46.         auto pr = split(t->r, key);
  47.         t->r = pr.first;
  48.         upd(t);
  49.         return {t, pr.second};
  50.     } else {
  51.         auto pr = split(t->l, key);
  52.         t->l = pr.second;
  53.         upd(t);
  54.         return {pr.first, t};
  55.     }
  56. }
  57.  
  58. Node* merge(Node* a, Node* b) {
  59.     if (!a) return b;
  60.     if (!b) return a;
  61.     push(a); push(b);
  62.     if (a->pr < b->pr) {
  63.         a->r = merge(a->r, b);
  64.         upd(a);
  65.         return a;
  66.     } else {
  67.         b->l = merge(a, b->l);
  68.         upd(b);
  69.         return b;
  70.     }
  71. }
  72.  
  73. int main() {
  74.     fast
  75.     int n;
  76.     if (!(cin >> n)) return 0;
  77.     vector<ll> a(n);
  78.     for (int i = 0; i < n; i++) {
  79.         cin >> a[i];
  80.     }
  81.     sort(a.begin(), a.end());
  82.     Node* root = nullptr;
  83.     vector<Node*> stk;
  84.     for (int i = 0; i < n; i++) {
  85.         Node* cur = new Node(a[i], uniform_int_distribution<int>(INT_MIN, INT_MAX)(rng));
  86.         Node* last = nullptr;
  87.         while (!stk.empty() && stk.back()->pr > cur->pr) {
  88.             last = stk.back();
  89.             stk.pop_back();
  90.         }
  91.         cur->l = last;
  92.         if (!stk.empty()) {
  93.             stk.back()->r = cur;
  94.         }
  95.         stk.push_back(cur);
  96.     }
  97.     while (stk.size() > 1) stk.pop_back();
  98.     if (!stk.empty()) root = stk[0];
  99.     function<void(Node*)> dfs_upd = [&](Node* u) {
  100.         if (!u) return;
  101.         push(u);
  102.         dfs_upd(u->l);
  103.         dfs_upd(u->r);
  104.         upd(u);
  105.     };
  106.     dfs_upd(root);
  107.  
  108.     int m;
  109.     cin >> m;
  110.     vector<ll> t(m);
  111.     for (int i = 0; i < m; i++) {
  112.         cin >> t[i];
  113.     }
  114.     for (int i = 0; i < m; i++) {
  115.         ll ti = t[i];
  116.         auto sp = split(root, ti);
  117.         Node* L = sp.first;
  118.         Node* R = sp.second;
  119.         ll cnt = getsz(R);
  120.         cout << cnt << "\n";
  121.         if (R) {
  122.             apply_lazy(R, -1);
  123.         }
  124.         root = merge(L, R);
  125.     }
  126.     return 0;
  127. }
  128.  
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rWTz7d
language:
C++ (gcc 8.3)
created:
3 days 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!