#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define endl '\n'
using namespace std;
mt19937 random_generator(chrono::steady_clock::now().time_since_epoch().count());
struct node
{
int x, y;
int lazy_x, lazy_y;
int prior;
node *l, *r, *par;
node() {}
node(int _x, int _y)
{
x = _x;
y = _y;
lazy_x = lazy_y = -1;
prior = random_generator();
l = r = par = nullptr;
}
};
void push(node *t)
{
if (!t)
return;
if (t->lazy_x != -1)
{
t->x = t->lazy_x;
if (t->l)
t->l->lazy_x = t->lazy_x;
if (t->r)
t->r->lazy_x = t->lazy_x;
t->lazy_x = -1;
}
if (t->lazy_y != -1)
{
t->y = t->lazy_y;
if (t->l)
t->l->lazy_y = t->lazy_y;
if (t->r)
t->r->lazy_y = t->lazy_y;
t->lazy_y = -1;
}
}
void pull(node *t)
{
if (!t)
return;
t->par = nullptr;
if (t->l)
t->l->par = t;
if (t->r)
t->r->par = t;
}
void split(node *t, pair <int, int> x, node *&l, node *&r)
{
push(t);
if (!t)
{
l = r = nullptr;
return;
}
if (t->x > x.first || t->y > x.second || (t->x == x.first && t->y == x.second && rand() % 2))
split(t->l, x, l, t->l), r = t;
else
split(t->r, x, t->r, r), l = t;
pull(t);
}
void merge_op(node *l, node *r, node *&t)
{
push(l);
push(r);
if (!l || !r)
{
t = l ? l : r;
return;
}
if (l->prior < r->prior)
swap(l, r);
node *ll, *rr;
split(r, make_pair(l->x, l->y), ll, rr);
merge_op(l->l, ll, l->l);
merge_op(l->r, rr, l->r);
t = l;
pull(t);
}
pair <int, int> leftmost(node *t)
{
push(t);
if (t->l)
return leftmost(t->l);
return {t->x, t->y};
}
struct treap
{
node *group;
int prior;
int x, y, min_y;
treap *l, *r;
treap() {}
treap(node *t)
{
group = t;
pair <int, int> curr = leftmost(t);
prior = random_generator();
x = curr.first;
y = min_y = curr.second;
l = r = nullptr;
}
};
void pull_treap(treap *t)
{
t->min_y = t->y;
if (t->l)
t->min_y = min(t->min_y, t->l->min_y);
if (t->r)
t->min_y = min(t->min_y, t->r->min_y);
}
void merge(treap *l, treap *r, treap *&t)
{
if (!l || !r)
{
t = l ? l : r;
return;
}
if (l->prior > r->prior)
merge(l->r, r, l->r), t = l;
else
merge(l, r->l, r->l), t = r;
pull_treap(t);
}
void split_treap(treap *t, int x, treap *&l, treap *&r)
{
if (!t)
{
l = r = nullptr;
return;
}
if (x < t->x)
split_treap(t->l, x, l, t->l), r = t;
else
split_treap(t->r, x, t->r, r), l = t;
pull_treap(t);
}
void insert(treap *&t, treap *x)
{
if (!t)
{
t = x;
return;
}
if (x->prior > t->prior)
{
split_treap(t, x->x - rand() % 2, x->l, x->r);
t = x;
pull_treap(t);
return;
}
if (x->x + rand() % 2 <= t->x)
insert(t->l, x);
else
insert(t->r, x);
pull_treap(t);
}
const int maxm = 500003;
node *where[maxm * 3];
treap *root = nullptr;
int n, m, q;
void read()
{
cin >> n >> m >> q;
for (int i = 1; i <= m; i++)
{
int x, y;
cin >> x >> y;
where[i] = new node(x, y);
insert(root, new treap(where[i]));
}
}
pair <int, int> get(node *t)
{
int lazy_x = t->x, lazy_y = t->y;
while (t)
{
if (t->lazy_x != -1)
lazy_x = t->lazy_x;
if (t->lazy_y != -1)
lazy_y = t->lazy_y;
t = t->par;
}
return {lazy_x, lazy_y};
}
vector <treap*> to_add;
node *all;
void clean1(treap *&x, int pos)
{
if (!x)
return;
if (x->x > n-pos)
{
clean1(x->l, pos);
return;
}
if (x->min_y > pos)
return;
clean1(x->l, pos);
clean1(x->r, pos);
if (x->y <= pos)
{
node *l, *r;
split(x->group, {n-pos, pos}, l, r);
if (l)
l->lazy_x = n-pos;
merge_op(all, l, all);
if (r)
to_add.push_back(new treap(r));
merge(x->l, x->r, x);
}
}
void clean2(treap *&x, int pos)
{
if (!x)
return;
if (x->x > pos)
{
clean2(x->l, pos);
return;
}
if (x->min_y > n-pos)
return;
clean2(x->l, pos);
clean2(x->r, pos);
if (x->y <= n-pos)
{
node *l, *r;
split(x->group, {pos, n-pos}, l, r);
if (l)
l->lazy_y = n-pos;
merge_op(all, l, all);
if (r)
to_add.push_back(new treap(r));
merge(x->l, x->r, x);
}
}
void solve()
{
int curr_idx = m + 1;
while (q--)
{
int type;
cin >> type;
if (type == 1)
{
int idx;
cin >> idx;
auto ans = get(where[idx]);
cout << ans.first << " " << ans.second << endl;
}
else
if (type == 2)
{
int x;
cin >> x;
all = nullptr;
to_add.clear();
clean1(root, x);
if (all)
insert(root, new treap(all));
for (auto i: to_add)
insert(root, i);
}
else
if (type == 3)
{
int x;
cin >> x;
all = nullptr;
to_add.clear();
clean2(root, x);
if (all)
insert(root, new treap(all));
for (auto i: to_add)
insert(root, i);
}
else
{
int x, y;
cin >> x >> y;
where[curr_idx] = new node(x, y);
insert(root, new treap(where[curr_idx]));
curr_idx++;
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
read();
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
876 KB |
Output is correct |
| 2 |
Correct |
7 ms |
620 KB |
Output is correct |
| 3 |
Correct |
5 ms |
876 KB |
Output is correct |
| 4 |
Correct |
8 ms |
876 KB |
Output is correct |
| 5 |
Correct |
12 ms |
1132 KB |
Output is correct |
| 6 |
Correct |
19 ms |
876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18022 ms |
60028 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1683 ms |
76708 KB |
Output is correct |
| 2 |
Correct |
1490 ms |
70540 KB |
Output is correct |
| 3 |
Correct |
1130 ms |
77596 KB |
Output is correct |
| 4 |
Correct |
2310 ms |
100844 KB |
Output is correct |
| 5 |
Correct |
1563 ms |
72744 KB |
Output is correct |
| 6 |
Correct |
1432 ms |
69868 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1683 ms |
76708 KB |
Output is correct |
| 2 |
Correct |
1490 ms |
70540 KB |
Output is correct |
| 3 |
Correct |
1130 ms |
77596 KB |
Output is correct |
| 4 |
Correct |
2310 ms |
100844 KB |
Output is correct |
| 5 |
Correct |
1563 ms |
72744 KB |
Output is correct |
| 6 |
Correct |
1432 ms |
69868 KB |
Output is correct |
| 7 |
Execution timed out |
18032 ms |
59708 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
876 KB |
Output is correct |
| 2 |
Correct |
7 ms |
620 KB |
Output is correct |
| 3 |
Correct |
5 ms |
876 KB |
Output is correct |
| 4 |
Correct |
8 ms |
876 KB |
Output is correct |
| 5 |
Correct |
12 ms |
1132 KB |
Output is correct |
| 6 |
Correct |
19 ms |
876 KB |
Output is correct |
| 7 |
Execution timed out |
18022 ms |
60028 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
