#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 1e9 + 9;
int grand() {
return ((ll)rand() << 15) + rand();
}
struct treap {
int x, y, i;
int set_x, set_y;
int pr;
treap *l, *r, *par;
treap(int x, int y, int i) : x(x), y(y), i(i), set_x(-1), set_y(-1), pr(grand()), l(0), r(0), par(0) {}
treap() {}
};
void upd(treap *t, int a, int b) {
if (!t)
return;
if (a != -1)
t->set_x = t->x = a;
if (b != -1)
t->set_y = t->y = b;
}
void push(treap *t) {
upd(t->l, t->set_x, t->set_y);
upd(t->r, t->set_x, t->set_y);
t->set_x = t->set_y = -1;
}
void s_p(treap *t, treap *p) { if (t) t->par = p; }
pair<treap *, treap *> split(treap *t, pair<int, int> k, int i = inf) {
if (!t)
return {0, 0};
push(t);
if (t->x > k.first || t->y > k.second || (k == make_pair(t->x, t->y) && t->i == i)) {
s_p(t->l, 0);
auto a = split(t->l, k, i);
t->l = a.second;
s_p(t->l, t);
return {a.first, t};
} else {
s_p(t->r, 0);
auto a = split(t->r, k, i);
t->r = a.first;
s_p(t->r, t);
return {t, a.second};
}
}
treap *merge(treap *a, treap *b) {
if (!a)
return b;
if (!b)
return a;
push(a), push(b);
if (a->pr > b->pr) {
s_p(a->r, 0);
a->r = merge(a->r, b);
s_p(a->r, a);
return a;
} else {
s_p(b->l, 0);
b->l = merge(a, b->l);
s_p(b->l, b);
return b;
}
}
treap *wtf_merge(treap *a, treap *b) { // почему это работает быстро?
if (!a)
return b;
if (!b)
return a;
push(a), push(b);
if (a->pr < b->pr)
swap(a, b);
auto sb = split(b, {a->x, a->y}, a->i);
s_p(a->l, 0), s_p(a->r, 0);
a->l = wtf_merge(a->l, sb.first), a->r = wtf_merge(a->r, sb.second);
s_p(a->l, a);
s_p(a->r, a);
return a;
}
pair<int, int> gl(treap *t) {
push(t);
if (t->l)
return gl(t->l);
return {t->x, t->y};
}
int n, m, q;
struct btreap {
treap *gr;
int x, y, mxy, pr;
btreap *l, *r;
btreap(treap *t) {
gr = t;
auto L = gl(t);
x = L.first, y = n - L.second;
mxy = y;
pr = grand();
l = r = 0;
}
btreap() {}
};
void upd(btreap *t) {
if (!t)
return;
t->mxy = t->y;
if (t->l)
t->mxy = max(t->mxy, t->l->mxy);
if (t->r)
t->mxy = max(t->mxy, t->r->mxy);
}
pair<btreap *, btreap *> split(btreap *t, int k, treap *x, bool inc) {
if (!t)
return {0, 0};
upd(t);
if (t->x > k || (t->x == k && inc && t->gr > x)) { // ???
auto a = split(t->l, k, x, inc);
t->l = a.second;
upd(t);
return {a.first, t};
} else {
auto a = split(t->r, k, x, inc);
t->r = a.first;
upd(t);
return {t, a.second};
}
}
btreap *merge(btreap *a, btreap *b) {
if (!a)
return b;
if (!b)
return a;
if (a->pr > b->pr) {
a->r = merge(a->r, b);
upd(a);
return a;
} else {
b->l = merge(b->l, a);
upd(b);
return b;
}
}
btreap *insert_btreap(btreap *t, treap *x) {
if (!x) return t;
btreap *ins = new btreap(x);
auto a = split(t, ins->x, x, true);
a.first = merge(a.first, ins);
return merge(a.first, a.second);
}
vector <treap *> trav;
btreap *traverse(btreap *t, int y) { // x <= l, y <= n - l -> l <= n - y -> l <= y_in_treap
if (!t || t->mxy < y)
return t;
if (t->y < y) {
t->l = traverse(t->l, y);
t->r = traverse(t->r, y);
upd(t);
return t;
} else {
trav.push_back(t->gr); // нашли челика из поддерева которого надо вытащить и его, и еще ребят
btreap *a = traverse(t->l, y);
btreap *b = traverse(t->r, y);
return merge(a, b);
}
}
btreap *groups = 0;
void sweep(int l) {
trav.clear();
auto a = split(groups, l, 0, false); // находим группы из которых нужно вытащить челиков
groups = a.second;
groups = merge(traverse(a.first, l), groups);
for (auto &dust : trav) {
auto x = split(dust, make_pair(l, n - l));
dust = x.first;
groups = insert_btreap(groups, x.second);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> q;
vector<treap *> ptr;
for (int i = 0; i < m; ++i) {
int x, y;
cin >> x >> y;
treap *ins = new treap(x, y, i);
groups = insert_btreap(groups, ins);
ptr.push_back(ins);
}
for (int i = 0; i < q; ++i) {
int t;
cin >> t;
if (t == 1) {
int p;
cin >> p;
p--;
treap *me = ptr[p];
vector<treap *> way;
while (me) {
way.push_back(me);
me = me->par;
}
for (int j = (int) way.size() - 1; j >= 0; --j)
push(way[j]);
cout << ptr[p]->x << ' ' << ptr[p]->y << '\n';
} else if (t == 2) {
int l;
cin >> l;
sweep(n - l);
treap *new_gr = 0;
for (auto dust : trav) {
upd(dust, n - l, -1);
new_gr = wtf_merge(new_gr, dust);
}
groups = insert_btreap(groups, new_gr);
} else if (t == 3) {
int l;
cin >> l;
sweep(l);
treap *new_gr = 0;
for (auto dust : trav) {
upd(dust, -1, n - l);
new_gr = wtf_merge(new_gr, dust);
}
groups = insert_btreap(groups, new_gr);
} else {
int x, y;
cin >> x >> y;
treap *ins = new treap(x, y, m);
m++;
groups = insert_btreap(groups, ins);
ptr.push_back(ins);
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
1004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3740 ms |
274832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1871 ms |
100712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1871 ms |
100712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
1004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
