Advertisement
Guest User

Untitled

a guest
Aug 14th, 2019
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.65 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. typedef long long ll;
  7.  
  8. #define x first
  9. #define y second
  10.  
  11. #undef merge
  12. #undef insert
  13.  
  14. const int INF = 1e9;
  15.  
  16. struct node {
  17. int prior, val, f, cnt, num;
  18. node * l, * r;
  19.  
  20. node() :
  21. l(nullptr),
  22. r(nullptr)
  23. {}
  24.  
  25. };
  26.  
  27. typedef node * ptr;
  28.  
  29. int cnt(ptr t) {
  30. if (t == nullptr) return 0;
  31. else {
  32. return t->cnt;
  33. }
  34. }
  35.  
  36. int f(ptr t) {
  37. if (t == nullptr) return -1;
  38. else {
  39. return t->f;
  40. }
  41. }
  42.  
  43. void upd(ptr t) {
  44. if (t != nullptr) {
  45. t->cnt = cnt(t->l) + cnt(t->r) + 1;
  46. t->f = max(t->val, max(f(t->l), f(t->r)));
  47. }
  48. }
  49.  
  50. void split(ptr t, ptr & l, ptr & r, int key, int add) {
  51. if (t == nullptr) {
  52. l = r = nullptr;
  53. return;
  54. }
  55. int cur_key = add + cnt(t->l);
  56. if (key <= cur_key) {
  57. split(t->l, l, t->l, key, add);
  58. r = t;
  59. } else {
  60. split(t->r, t->r, r, key, cur_key + 1);
  61. l = t;
  62. }
  63. upd(t);
  64. }
  65.  
  66. void merge(ptr & t, ptr l, ptr r) {
  67. if (l == nullptr) t = r;
  68. else if (r == nullptr) t = l;
  69. else {
  70. if (l->prior > r->prior) {
  71. merge(l->r, l->r, r);
  72. t = l;
  73. } else {
  74. merge(r->l, l, r->l);
  75. t = r;
  76. }
  77. }
  78. upd(t);
  79. }
  80.  
  81. void insert(ptr & t, int pos, ptr vertex) {
  82. if (t == nullptr) {
  83. t = vertex;
  84. return;
  85. }
  86. ptr t1 = nullptr, t2 = nullptr;
  87. split(t, t1, t2, pos, 0);
  88. merge(t1, t1, vertex);
  89. merge(t, t1, t2);
  90. }
  91.  
  92. int get(int l, int r, ptr t) {
  93. if (t == nullptr) {
  94. return 0;
  95. }
  96. ptr t1, t2, t3;
  97. split(t, t1, t2, l, 0);
  98. split(t2, t2, t3, r - l + 1, 0);
  99. int ans = t2->f;
  100. merge(t, t1, t2);
  101. merge(t, t, t3);
  102. return ans;
  103. }
  104.  
  105. void print(ptr t) {
  106. if (t == nullptr) {
  107. return;
  108. } else {
  109. print(t->l);
  110. cout << t->num << ' ';
  111. print(t->r);
  112. }
  113. }
  114.  
  115. int main() {
  116. ios::sync_with_stdio(0);
  117. cin.tie(nullptr);
  118. srand(22823978567);
  119.  
  120. ptr tree = nullptr;
  121.  
  122. int n; cin >> n;
  123. for (int i = 0; i < n; ++i) {
  124. int a, c;
  125. cin >> a >> c;
  126. ptr v = new node();
  127. v->val = v->f = a;
  128. v->num = i + 1;
  129. v->prior = rand() % INF;
  130. int l = max(-1, i - c - 1);
  131. int r = i;
  132. while (l + 1 < r) {
  133. int m = l + (r - l) / 2;
  134. if (get(m, i - 1, tree) < a) {
  135. r = m;
  136. } else {
  137. l = m;
  138. }
  139. }
  140. insert(tree, r, v);
  141. }
  142.  
  143. print(tree);
  144. return 0;
  145. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement