#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)
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);
}
struct segtree
{
set <node*> s;
segtree *l, *r;
segtree() {s.clear(), l = r = nullptr;}
};
void range_update(segtree *tr, int l, int r, int ll, int rr, node *&to_add)
{
if (l > rr || r < ll || ll > rr)
return;
if (l >= ll && r <= rr)
{
tr->s.insert(to_add);
return;
}
int mid = (l + r) / 2;
if (!tr->l)
tr->l = new segtree();
if (!tr->r)
tr->r = new segtree();
range_update(tr->l, l, mid, ll, rr, to_add);
range_update(tr->r, mid + 1, r, ll, rr, to_add);
}
void remove(segtree *tr, int l, int r, int ll, int rr, node *&to_remove)
{
if (l > rr || r < ll || ll > rr)
return;
if (l >= ll && r <= rr)
{
tr->s.erase(to_remove);
return;
}
int mid = (l + r) / 2;
if (tr->l)
remove(tr->l, l, mid, ll, rr, to_remove);
if (tr->r)
remove(tr->r, mid + 1, r, ll, rr, to_remove);
}
pair <int, int> leftmost(node *t)
{
push(t);
if (t->l)
return leftmost(t->l);
return {t->x, t->y};
}
const int maxm = 500003;
node *where[maxm * 3];
segtree *tr1 = new segtree(), *tr2 = new segtree();
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);
range_update(tr1, 0, n, y, n-x, where[i]);
range_update(tr2, 0, n, x, n-y, where[i]);
}
}
void change1(segtree *tr, int l, int r, int pos, node *&to_add)
{
vector <node*> vec(tr->s.begin(), tr->s.end());
for (auto i: vec)
{
pair <int, int> curr = leftmost(i);
/*
if (curr.second < pos || curr.first > n-pos)
{
cout << pos << endl;
exit(0);
}
assert(curr.second >= pos && curr.first <= n-pos);
*/
remove(tr1, 0, n, curr.second, n - curr.first, i);
remove(tr2, 0, n, curr.first, n - curr.second, i);
node *l, *r;
split(i, {n-pos, pos}, l, r);
if (r)
{
curr = leftmost(r);
range_update(tr1, 0, n, curr.second, n - curr.first, r);
range_update(tr2, 0, n, curr.first, n - curr.second, r);
}
if (l)
l->lazy_x = n-pos;
merge_op(to_add, l, to_add);
}
vec.clear();
vec.shrink_to_fit();
if (l == r)
return;
int mid = (l + r) / 2;
if (tr->l && pos <= mid)
change1(tr->l, l, mid, pos, to_add);
if (tr->r && pos > mid)
change1(tr->r, mid + 1, r, pos, to_add);
}
void change2(segtree *tr, int l, int r, int pos, node *&to_add)
{
vector <node*> vec(tr->s.begin(), tr->s.end());
for (auto i: vec)
{
pair <int, int> curr = leftmost(i);
/*
if (curr.first > pos || curr.second > n-pos)
{
assert(i == where[1]);
cout << pos << " " << l << " " << r << " " << curr.first << " " << curr.second << endl;
exit(0);
}
assert(curr.first >= pos && curr.second <= n-pos);
*/
remove(tr1, 0, n, curr.second, n - curr.first, i);
remove(tr2, 0, n, curr.first, n - curr.second, i);
node *l, *r;
split(i, {pos, n-pos}, l, r);
if (r)
{
curr = leftmost(r);
range_update(tr1, 0, n, curr.second, n - curr.first, r);
range_update(tr2, 0, n, curr.first, n - curr.second, r);
}
if (l)
l->lazy_y = n-pos;
merge_op(to_add, l, to_add);
}
vec.clear();
vec.shrink_to_fit();
if (l == r)
return;
int mid = (l + r) / 2;
if (tr->l && pos <= mid)
change2(tr->l, l, mid, pos, to_add);
if (tr->r && pos > mid)
change2(tr->r, mid + 1, r, pos, to_add);
}
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};
}
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;
node *to_add = nullptr;
change1(tr1, 0, n, x, to_add);
if (!to_add)
continue;
auto curr = leftmost(to_add);
range_update(tr1, 0, n, curr.second, n-curr.first, to_add);
range_update(tr2, 0, n, curr.first, n-curr.second, to_add);
}
else
if (type == 3)
{
int x;
cin >> x;
node *to_add = nullptr;
change2(tr2, 0, n, x, to_add);
if (!to_add)
continue;
auto curr = leftmost(to_add);
range_update(tr1, 0, n, curr.second, n-curr.first, to_add);
range_update(tr2, 0, n, curr.first, n-curr.second, to_add);
}
else
{
int x, y;
cin >> x >> y;
where[curr_idx] = new node(x, y);
range_update(tr1, 0, n, y, n-x, where[curr_idx]);
range_update(tr2, 0, n, x, n-y, 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 |
107 ms |
36972 KB |
Output is correct |
| 2 |
Correct |
49 ms |
20204 KB |
Output is correct |
| 3 |
Correct |
39 ms |
14188 KB |
Output is correct |
| 4 |
Correct |
101 ms |
36204 KB |
Output is correct |
| 5 |
Correct |
26 ms |
2284 KB |
Output is correct |
| 6 |
Correct |
71 ms |
896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5482 ms |
2097156 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3329 ms |
2097156 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3329 ms |
2097156 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
107 ms |
36972 KB |
Output is correct |
| 2 |
Correct |
49 ms |
20204 KB |
Output is correct |
| 3 |
Correct |
39 ms |
14188 KB |
Output is correct |
| 4 |
Correct |
101 ms |
36204 KB |
Output is correct |
| 5 |
Correct |
26 ms |
2284 KB |
Output is correct |
| 6 |
Correct |
71 ms |
896 KB |
Output is correct |
| 7 |
Runtime error |
5482 ms |
2097156 KB |
Execution killed with signal 9 |
| 8 |
Halted |
0 ms |
0 KB |
- |
