#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
return l + rd() % (r - l + 1);
}
const int N = 2e6 + 5;
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);
struct trie {
struct node {
int cnt;
int ptr[2];
node(int _cnt = 0) {
cnt = _cnt;
for (int i = 0; i < 2; i++)
ptr[i] = 0;
}
};
vector <node> tree;
int node,sz;
#define ptr(cur, i) tree[cur].ptr[i]
#define cnt(cur) tree[cur].cnt
trie() {
node = 0;
sz = 0;
tree.emplace_back();
}
void add(int x, int val) {
sz += val;
int cur = 0;
for (int i = 29; i >= 0; i--) {
int v = getbit(x, i);
if (!ptr(cur, v)) {
ptr(cur, v) = ++node;
tree.emplace_back();
}
cur = ptr(cur, v);
cnt(cur)++;
}
}
int getcnt(int x) {
int cur = 0;
int res = 0;
for (int i = 29; i >= 0; i--) {
int v = getbit(x, i);
for (int j = 0; j < v; j++)
res += cnt(ptr(cur, j));
cur = ptr(cur, v);
if (cur == 0)
break;
}
return res;
}
};
vector <trie> tx, ty;
map <int, int> posx;
set <pair <int, int>> sx[N], sy[N];
trie block[N];
int curx[N];
int cury[N];
int ind[N];
int bk[N];
int op[N];
int x[N];
int y[N];
int n,m,q,nDust,nBlock;
void change(int i, int newb) {
int curb = bk[i];
// cerr << i << " " << curb << " " << newb << "\n";
tx[curb].add(x[i], -1);
ty[curb].add(y[i], -1);
sx[curb].erase(mp(x[i], i));
sy[curb].erase(mp(y[i], i));
assert(curb != newb);
bk[i] = newb;
tx[newb].add(x[i], 1);
ty[newb].add(y[i], 1);
sx[newb].insert(mp(x[i], i));
sy[newb].insert(mp(y[i], i));
}
void sub1() {
posx[0] = 0;
tx.emplace_back(), ty.emplace_back();
for (int i = 1; i <= m; i++) {
sx[0].insert(mp(x[i], i));
sy[0].insert(mp(y[i], i));
tx[0].add(x[i], 1);
ty[0].add(y[i], 1);
bk[i] = 0;
}
for (int i = m + 1; i <= q; i++) {
// cerr << "query " << i << "\n";
if (op[i] == 1) {
int id = ind[i];
cout << max(curx[bk[id]], x[id])
<< " " << max(cury[bk[id]], y[id]) << "\n";
} else if (op[i] == 2) {
int Lx = n - x[i];
int Ly = x[i];
// cerr << i << " " << Lx << " " << Ly << "\n";
if (posx.count(Lx) == 0) {
int pre = prev(posx.upper_bound(Lx))->se;
int up = ty[pre].getcnt(Ly + 1);
int dn = ty[pre].sz - up;
posx[Lx] = ++nBlock;
curx[nBlock] = Lx;
cury[nBlock] = cury[pre];
cury[pre] = Ly;
tx.emplace_back();
ty.emplace_back();
int cur = nBlock;
if (up < dn) {
while (sy[pre].size()) {
auto it = prev(sy[pre].end());
if (max(cury[pre], y[it->se]) <= Ly)
break;
// cerr << pre << " " << cur << " " << it->se << "\n";
change(it->se, cur);
}
swap(posx[Lx], posx[curx[pre]]);
swap(curx[pre], curx[cur]);
swap(cury[pre], cury[cur]);
} else {
while (sy[pre].size()) {
auto it = sy[pre].begin();
if (max(cury[pre], y[it->se]) > Ly)
break;
change(it->se, cur);
}
}
}
} else {
int Lx = x[i] + 1;
int Ly = n - x[i];
if (posx.count(Lx) == 0) {
int pre = prev(posx.lower_bound(Lx))->se;
int lf = tx[pre].getcnt(Lx + 1);
int rt = tx[pre].sz - lf;
posx[Lx] = ++nBlock;
curx[nBlock] = Lx;
cury[nBlock] = cury[pre];
cury[pre] = Ly;
tx.emplace_back();
ty.emplace_back();
int cur = nBlock;
if (lf > rt) {
while (sx[pre].size()) {
auto it = prev(sx[pre].end());
if (max(curx[pre], x[it->se]) < Lx)
break;
change(it->se, cur);
}
} else {
while (sx[pre].size()) {
auto it = sx[pre].begin();
if (max(curx[pre], x[it->se]) >= Lx)
break;
change(it->se, cur);
}
swap(posx[Lx], posx[curx[pre]]);
swap(curx[pre], curx[cur]);
swap(cury[pre], cury[cur]);
}
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
#ifdef ONLINE_JUDGE
// freopen(TASK".inp","r",stdin);
// freopen(TASK".out","w",stdout);
#endif
cin >> n >> m >> q;
for (int i = 1; i <= m; i++) {
op[i] = 4;
cin >> x[i] >> y[i];
}
q += m;
for (int i = m + 1; i <= q; i++) {
cin >> op[i];
assert(op[i] <= 3);
if (op[i] == 1) {
cin >> ind[i];
} else if (op[i] <= 3) {
cin >> x[i];
} else
cin >> x[i] >> y[i];
}
sub1();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
433 ms |
635428 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
528 ms |
657116 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7345 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7345 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
433 ms |
635428 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
