SHARE
TWEET

Untitled

a guest Aug 14th, 2019 53 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top