fork download
  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
stdin
Standard input is empty
stdout
20