Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- #define x first
- #define y second
- #undef merge
- #undef insert
- const int INF = 1e9;
- struct node {
- int prior, val, f, cnt, num;
- node * l, * r;
- node() :
- l(nullptr),
- r(nullptr)
- {}
- };
- typedef node * ptr;
- int cnt(ptr t) {
- if (t == nullptr) return 0;
- else {
- return t->cnt;
- }
- }
- int f(ptr t) {
- if (t == nullptr) return -1;
- else {
- return t->f;
- }
- }
- void upd(ptr t) {
- if (t != nullptr) {
- t->cnt = cnt(t->l) + cnt(t->r) + 1;
- t->f = max(t->val, max(f(t->l), f(t->r)));
- }
- }
- void split(ptr t, ptr & l, ptr & r, int key, int add) {
- if (t == nullptr) {
- l = r = nullptr;
- return;
- }
- int cur_key = add + cnt(t->l);
- if (key <= cur_key) {
- split(t->l, l, t->l, key, add);
- r = t;
- } else {
- split(t->r, t->r, r, key, cur_key + 1);
- l = t;
- }
- upd(t);
- }
- void merge(ptr & t, ptr l, ptr r) {
- if (l == nullptr) t = r;
- else if (r == nullptr) t = l;
- else {
- if (l->prior > r->prior) {
- merge(l->r, l->r, r);
- t = l;
- } else {
- merge(r->l, l, r->l);
- t = r;
- }
- }
- upd(t);
- }
- void insert(ptr & t, int pos, ptr vertex) {
- if (t == nullptr) {
- t = vertex;
- return;
- }
- ptr t1 = nullptr, t2 = nullptr;
- split(t, t1, t2, pos, 0);
- merge(t1, t1, vertex);
- merge(t, t1, t2);
- }
- int get(int l, int r, ptr t) {
- if (t == nullptr) {
- return 0;
- }
- ptr t1, t2, t3;
- split(t, t1, t2, l, 0);
- split(t2, t2, t3, r - l + 1, 0);
- int ans = t2->f;
- merge(t, t1, t2);
- merge(t, t, t3);
- return ans;
- }
- void print(ptr t) {
- if (t == nullptr) {
- return;
- } else {
- print(t->l);
- cout << t->num << ' ';
- print(t->r);
- }
- }
- int main() {
- ios::sync_with_stdio(0);
- cin.tie(nullptr);
- srand(22823978567);
- ptr tree = nullptr;
- int n; cin >> n;
- for (int i = 0; i < n; ++i) {
- int a, c;
- cin >> a >> c;
- ptr v = new node();
- v->val = v->f = a;
- v->num = i + 1;
- v->prior = rand() % INF;
- int l = max(-1, i - c - 1);
- int r = i;
- while (l + 1 < r) {
- int m = l + (r - l) / 2;
- if (get(m, i - 1, tree) < a) {
- r = m;
- } else {
- l = m;
- }
- }
- insert(tree, r, v);
- }
- print(tree);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement