fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #include <algorithm>
  4. #ifdef ONLINE_JUDGE
  5. #define endl "\n"
  6. #endif
  7. using namespace std;
  8. typedef long long LL;
  9. typedef vector<int> VI;
  10. typedef vector<VI> VVI;
  11. typedef pair<int, int> PII;
  12.  
  13. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  14. // mt19937 rng(100);
  15. VI answer;
  16.  
  17. template <typename T>
  18. struct Node {
  19.     T val, count;
  20.     T lazycount, lazysub;
  21.  
  22.     int pos;
  23.     int prior;
  24.     Node *l, *r;
  25.  
  26.     inline void set(T _val, int idx) {
  27.         pos = idx;
  28.         val = _val;
  29.     }
  30.     Node()
  31.         : count(0),
  32.           lazycount(0),
  33.           lazysub(0),
  34.           l(nullptr),
  35.           r(nullptr),
  36.           prior(rng()) {
  37.     }
  38. };
  39. Node<int> nodes[200000 + 1];
  40. int nodecount = 0;
  41. using pnode = Node<int> *;
  42.  
  43. // tick
  44. inline void pushlazy(pnode t) {
  45.     if (not t)
  46.         return;
  47.     if (t->lazycount) {
  48.         t->count += t->lazycount;
  49.         t->val += t->lazysub;
  50.  
  51.         if (t->l)
  52.             t->l->lazycount += t->lazycount, t->l->lazysub += t->lazysub;
  53.         if (t->r)
  54.             t->r->lazycount += t->lazycount, t->r->lazysub += t->lazysub;
  55.  
  56.         t->lazycount = 0;
  57.         t->lazysub = 0;
  58.     }
  59. }
  60.  
  61. // tick
  62. void split_by_val(pnode t, pnode &l, pnode &r, int val) {
  63.     if (not t) {
  64.         l = r = nullptr;
  65.         return;
  66.     }
  67.  
  68.     pushlazy(t);
  69.  
  70.     if (t->val <= val) {
  71.         split_by_val(t->r, t->r, r, val);
  72.         l = t;
  73.     } else {
  74.         split_by_val(t->l, l, t->l, val);
  75.         r = t;
  76.     }
  77. }
  78.  
  79. // tick
  80. void merge(pnode &t, pnode l, pnode r) {
  81.     pushlazy(l);
  82.     pushlazy(r);
  83.     if (not l or not r)
  84.         t = l ? l : r;
  85.     else if (l->prior > r->prior) {
  86.         merge(l->r, l->r, r);
  87.         t = l;
  88.     } else {
  89.         merge(r->l, l, r->l);
  90.         t = r;
  91.     }
  92. }
  93.  
  94. void decrement(pnode t, int val) {
  95.     if (t) {
  96.         t->lazysub -= val;
  97.         t->lazycount += 1;
  98.     }
  99. }
  100.  
  101. // tick
  102. void gen_answer(pnode t) {
  103.     if (not t)
  104.         return;
  105.     pushlazy(t);
  106.     gen_answer(t->l);
  107.     assert(answer[t->pos] == -1);
  108.     answer[t->pos] = t->count;
  109.     gen_answer(t->r);
  110. }
  111.  
  112. // tick
  113. void insert_by_val(pnode &t, pnode it) {
  114.     if (not t) {
  115.         t = it;
  116.         return;
  117.     }
  118.     if (not it)
  119.         return;
  120.     pushlazy(t);
  121.     if (it->prior > t->prior) {
  122.         split_by_val(t, it->l, it->r, it->val);
  123.         t = it;
  124.     } else if (t->val <= it->val)
  125.         insert_by_val(t->r, it);
  126.     else
  127.         insert_by_val(t->l, it);
  128. }
  129.  
  130. void insert_all(pnode &target, pnode source) {
  131.     if (not source)
  132.         return;
  133.     pushlazy(source);
  134.     insert_all(target, source->l);
  135.     insert_all(target, source->r);
  136.     source->l = source->r = nullptr;
  137.     insert_by_val(target, source);
  138. }
  139.  
  140. int maxdepth = 0;
  141. void preorder(pnode treap, int depth = 0) {
  142.     if (treap) {
  143.         maxdepth = max(maxdepth, depth);
  144.         // cout << treap->pos << ": ";
  145.         // cout << (treap->l ? treap->l->pos : -1) << " ";
  146.         // cout << (treap->r ? treap->r->pos : -1) << endl;
  147.  
  148.         preorder(treap->l, depth + 1);
  149.         preorder(treap->r, depth + 1);
  150.     }
  151. }
  152.  
  153. int main() {
  154.     ios::sync_with_stdio(false);
  155.     cin.tie(nullptr);
  156.  
  157.     Node<int> *treap = nullptr;
  158.     int n = 1000;
  159.     for (int i = 0; i < n; i++) {
  160.         auto nd = new Node<int>();
  161.         nd->set(0, i);
  162.         insert_by_val(treap, nd);
  163.     }
  164.  
  165.     preorder(treap);
  166.     cout << maxdepth << endl;
  167.  
  168.     return 0;
  169. }
  170.  
Success #stdin #stdout 0.01s 11520KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
20
https://ideone.com/L5dI5C
language:
C++14 (gcc 8.3)
created:
2 years 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!