#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 5e5 + 10;
int n, m, q;
int X[N], Y[N];
struct Point {
int x, y, i;
int operator < (const Point& other) const {
if (x ^ other.x) return x < other.x;
if (y ^ other.y) return y < other.y;
return i < other.i;
}
} P[N];
set <Point> bX[N], bY[N];
int cnt_block = 1;
set <tuple <int, int, int> > ranges;
int block[N];
void DivideX(int id, int L, auto iter) {
++cnt_block;
X[cnt_block] = m - L;
while (bY[id].size()) {
auto [x, y, i] = *bY[id].begin();
if (x > L) break;
block[i] = cnt_block;
bY[id].erase({x, y, i});
bX[id].erase({y, x, i});
bY[cnt_block].insert({x, y, i});
bX[cnt_block].insert({y, x, i});
}
ranges.insert({get<0>(*iter), L, cnt_block});
ranges.insert({L, get<1>(*iter), id});
ranges.erase(iter);
}
void DivideY(int id, int L, auto iter) {
++cnt_block;
Y[cnt_block] = m - L;
while (bX[id].size()) {
auto [x, y, i] = *bX[id].begin();
if (x > L) break;
block[i] = cnt_block;
bX[id].erase({x, y, i});
bY[id].erase({y, x, i});
bX[cnt_block].insert({x, y, i});
bY[cnt_block].insert({y, x, i});
}
ranges.insert({get<0>(*iter), m - L, id});
ranges.insert({m - L, get<1>(*iter), cnt_block});
ranges.erase(iter);
}
int main() {
// freopen("test.inp", "r", stdin);
// freopen("test.out", "w", stdout);
ios :: sync_with_stdio(0); cin.tie(0);
cin >> m >> n >> q;
for (int i = 1; i <= n; ++i) {
int x, y;
cin >> x >> y;
P[i] = {x, y, i};
bX[cnt_block].insert({x, y, i});
bY[cnt_block].insert({y, x, i});
}
ranges.insert({0, m, 1});
while (q--) {
int cmd;
cin >> cmd;
if (cmd == 1) {
int i;
cin >> i;
cout << max(P[i].x, X[block[i]]) << ' ' << max(P[i].y, Y[block[i]]) << '\n';
} else if (cmd == 2) {
int L;
cin >> L;
auto iter = --ranges.lower_bound({L, (int)1e9, 0});
if (get<0>(*iter) == L) {
X[get<2>(*iter)] = max(X[get<0>(*iter)], m - L);
if (iter != ranges.begin()) {
--iter;
X[get<2>(*iter)] = max(X[get<2>(*iter)], m - L);
}
continue;
}
DivideX(get<2>(*iter), L, iter);
} else if (cmd == 3) {
int L;
cin >> L;
auto iter = --ranges.lower_bound({m - L, (int)1e9, 0});
if (get<0>(*iter) == m - L) {
Y[get<2>(*iter)] = max(Y[get<2>(*iter)], m - L);
if (iter != ranges.begin()) {
--iter;
Y[get<2>(*iter)] = max(Y[get<2>(*iter)], m - L);
}
continue;
}
DivideY(get<2>(*iter), L, iter);
} else {
assert(0);
}
}
}
Compilation message
sweeping.cpp:33:29: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
33 | void DivideX(int id, int L, auto iter) {
| ^~~~
sweeping.cpp: In function 'void DivideX(int, int, auto:1)':
sweeping.cpp:37:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
37 | auto [x, y, i] = *bY[id].begin();
| ^
sweeping.cpp: At global scope:
sweeping.cpp:50:29: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
50 | void DivideY(int id, int L, auto iter) {
| ^~~~
sweeping.cpp: In function 'void DivideY(int, int, auto:2)':
sweeping.cpp:54:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
54 | auto [x, y, i] = *bX[id].begin();
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
58 ms |
96332 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1944 ms |
248432 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5590 ms |
182748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5590 ms |
182748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
58 ms |
96332 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
