#include <bits/stdc++.h>
using namespace std;
using ll = long long;
mt19937 rnd(228);
void ckmax(int &x, int y) {
if (x < y) {
x = y;
}
}
struct Node {
int prior = 0, sz = 0;
int x = 0, y = 0, mxy = 0;
int pushx = -1, pushy = -1;
int L = 0, R = 0, par = 0;
Node() = default;
Node(int prior, int x, int y, int siz) : prior(prior), x(x), y(y), sz(siz), mxy(y) {}
};
vector<Node> t{{}};
int create(Node b = Node()) {
t.emplace_back(b);
return t.size() - 1;
}
void apply(int p, int pushx, int pushy) {
if (p == 0) {
return;
}
ckmax(t[p].x, pushx);
ckmax(t[p].pushx, pushx);
ckmax(t[p].y, pushy);
ckmax(t[p].pushy, pushy);
ckmax(t[p].mxy, t[p].y);
}
void push(int x) {
for (int p : {t[x].L, t[x].R}) {
apply(p, t[x].pushx, t[x].pushy);
}
t[x].pushx = t[x].pushy = -1;
}
void pull(int x) {
t[x].sz = 1 + t[t[x].L].sz + t[t[x].R].sz;
t[x].mxy = max({t[x].y, t[t[x].L].y, t[t[x].R].y});
for (int p : {t[x].L, t[x].R}) {
if (p) {
t[p].par = x;
}
}
}
int merge(int l, int r) {
if (!l || !r) {
return l ^ r;
}
push(l), push(r);
if (t[l].prior > t[r].prior) {
t[l].R = merge(t[l].R, r);
pull(l);
return l;
} else {
t[r].L = merge(l, t[r].L);
pull(r);
return r;
}
}
//key <= k
pair<int, int> split_x(int x, int k) {
if (!x) {
return {};
}
t[x].par = 0;
push(x);
if (t[x].x > k) {
auto se = split_x(t[x].L, k);
t[x].L = se.second;
pull(x);
return {se.first, x};
} else {
auto se = split_x(t[x].R, k);
t[x].R = se.first;
pull(x);
return {x, se.second};
}
}
int super_merge(int x, int y) {
t[x].par = t[y].par = 0;
if (!x || !y) {
return x ^ y;
}
push(x), push(y);
if (t[x].prior < t[y].prior) {
swap(x, y);
}
auto [l, r] = split_x(y, t[x].x);
t[x].L = super_merge(t[x].L, l);
t[x].R = super_merge(t[x].R, r);
pull(x);
return x;
}
//left.y <= k
pair<int, int> split_y(int x, int k) {
t[x].par = 0;
if (!x || t[x].mxy <= k) {
return {x, 0};
}
push(x);
auto [ly, lx] = split_y(t[x].L, k);
auto [ry, rx] = split_y(t[x].R, k);
if (t[x].y <= k) {
t[x].L = ly, t[x].R = ry;
pull(x);
return {x, merge(lx, rx)};
} else {
t[x].L = lx, t[x].R = rx;
pull(x);
return {merge(ly, ry), x};
}
}
pair<int, int> getValue(int x) {
int px = t[x].x, py = t[x].y;
while (x > 0) {
ckmax(px, t[x].pushx);
ckmax(py, t[x].pushy);
x = t[x].par;
}
return {px, py};
}
void debug_node(int x, string pref = "") {
if (!x) {
return;
}
pref += "->" + to_string(x);
debug_node(t[x].L, pref);
cout << pref << endl;
debug_node(t[x].R, pref);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, q;
cin >> n >> m >> q;
vector<int> pos(m + q);
int root = 0;
vector<int> X(m), Y(m), ord(m);
for (int i = 0; i < m; ++i) {
cin >> X[i] >> Y[i];
}
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int i, int j) {
return X[i] < X[j];
});
for (int i : ord) {
int x = X[i], y = Y[i];
pos[i] = create(Node(rnd(), x, y, 1));
root = merge(root, pos[i]);
}
for (int qwq = 1; qwq <= q; ++qwq) {
int T;
cin >> T;
if (T == 1) {
int p;
cin >> p;
auto [x, y] = getValue(pos[p - 1]);
cout << x << " " << y << '\n';
} else if (T == 2) {
int H;
cin >> H;
auto [l, r] = split_y(root, H);
apply(l, n - H, 0);
root = super_merge(l, r);
} else if (T == 3) {
int V;
cin >> V;
auto [l, r] = split_x(root, V);
apply(l, 0, n - V);
root = merge(l, r);
} else {
int x, y;
cin >> x >> y;
pos[m] = create(Node(rnd(), x, y, 1));
auto [l, r] = split_x(root, x);
root = merge(l, merge(pos[m], r));
m += 1;
}
}
return 0;
}
Compilation message
sweeping.cpp: In constructor 'Node::Node(int, int, int, int)':
sweeping.cpp:16:16: warning: 'Node::y' will be initialized after [-Wreorder]
16 | int x = 0, y = 0, mxy = 0;
| ^
sweeping.cpp:15:20: warning: 'int Node::sz' [-Wreorder]
15 | int prior = 0, sz = 0;
| ^~
sweeping.cpp:21:5: warning: when initialized here [-Wreorder]
21 | Node(int prior, int x, int y, int siz) : prior(prior), x(x), y(y), sz(siz), mxy(y) {}
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
724 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
524 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
18063 ms |
42544 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
18049 ms |
42540 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
18049 ms |
42540 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
724 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
524 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
