/*
ЗАПУСКАЕМ
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░
*/
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
#include <array>
using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; }
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left228
#define right right228
#define rank rank228
#define y1 y1228
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
#define mp make_pair
using ll = long long;
using ld = long double;
const int MAXMEM = 1000 * 1000 * 1024;
char _memory[MAXMEM];
size_t _ptr = 0;
void* operator new(size_t _x) { _ptr += _x; return _memory + _ptr - _x; }
void operator delete (void*) noexcept {}
const string FILENAME = "input";
const int MAXN = 1500228;
int parent[MAXN * 2];
struct dsu {
vector<int> val;
vector<vector<int> > realParent;
void init() {
val.clear();
realParent.clear();
}
int add(int v, int col) {
int id = sz(val);
val.pb(v);
realParent.emplace_back();
if (col != -1) {
parent[col] = id;
realParent.back().pb(col);
}
return id;
}
int unite(int x, int y) {
if (sz(realParent[x]) < sz(realParent[y])) {
swap(x, y);
}
chkmax(val[x], val[y]);
for (auto &t: realParent[y]) {
parent[t] = x;
realParent[x].pb(t);
}
return x;
}
int get(int x) {
return val[parent[x]];
}
};
dsu tr;
struct comp {
bool operator()(const int a, const int b) {
return tr.val[a] > tr.val[b];
}
};
int xpos[MAXN], ypos[MAXN];
pair<int, int> getPos(int x) {
return mp(tr.get(2 * x), tr.get(2 * x + 1));
}
int n, m, q;
bool was[MAXN];
pair<int, int> ans[MAXN], pos[MAXN];
void solve(int x, int y, vector<vector<int> > v) {
if (v.empty()) {
return;
}
int dif = n - x - y;
if (dif == 0) {
for (auto &t: v) {
if (t[0] == 1) {
ans[t[2]] = {x, y};
}
}
return;
}
tr.init();
int X = x + (dif + 1) / 2, Y = y + dif / 2 + 1;
vector<vector<int> > upper, right;
priority_queue<int, vector<int>, comp> qx, qy;
for (auto &t: v) {
if (t[0] == 1) {
if (pos[t[1]].second >= Y) {
upper.pb(t);
} else if (pos[t[1]].first >= X) {
right.pb(t);
} else {
ans[t[2]] = getPos(t[1]);
}
} else if (t[0] == 2) {
if (t[1] >= Y) {
int z = n - t[1];
int as = tr.add(z, -1);
while (sz(qx) && tr.val[qx.top()] < z) {
int x = qx.top();
qx.pop();
as = tr.unite(as, x);
}
qx.push(as);
upper.pb(t);
} else {
while (sz(qy) && tr.val[qy.top()] <= t[1]) {
int x = qy.top();
qy.pop();
for (auto &u: tr.realParent[x]) {
u /= 2;
if (!was[u]) {
pos[u] = getPos(u);
pos[u].first = n - t[1];
was[u] = 1;
right.pb({4, u, -1});
}
}
}
right.pb(t);
}
} else if (t[0] == 3) {
if (t[1] >= X) {
int z = n - t[1];
int as = tr.add(z, -1);
while (sz(qy) && tr.val[qy.top()] < z) {
int x = qy.top();
qy.pop();
as = tr.unite(as, x);
}
qy.push(as);
right.pb(t);
} else {
while (sz(qx) && tr.val[qx.top()] <= t[1]) {
int x = qx.top(); qx.pop();
for (auto &u: tr.realParent[x]) {
u /= 2;
if (!was[u]) {
pos[u] = getPos(u);
pos[u].second = n - t[1];
was[u] = 1;
upper.pb({4, u, -1});
}
}
}
upper.pb(t);
}
} else if (t[0] == 4) {
was[t[1]] = 0;
pair<int, int> p = pos[t[1]];
if (p.second >= Y) {
was[t[1]] = 1;
upper.pb(t);
} else if (p.first >= X) {
was[t[1]] = 1;
right.pb(t);
} else {
qx.push(tr.add(p.first, 2 * t[1]));
qy.push(tr.add(p.second, 2 * t[1] + 1));
}
}
}
solve(x, Y, upper);
solve(X, y, right);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// read(FILENAME);
cin >> n >> m >> q;
int cnt = 0;
vector<vector<int> > cur;
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
pos[++cnt] = {x ,y};
cur.pb({4, cnt, 0});
}
for (int i = 0; i < q; i++) {
ans[i] = {-1, -1};
int t;
cin >> t;
if (t <= 3) {
int p;
cin >> p;
cur.pb({t, p, i});
} else {
int a, b;
cin >> a >> b;
pos[++cnt] = {a, b};
cur.pb({t, cnt, i});
}
}
solve(0, 0, cur);
for (int i = 0; i < q; i++) {
if (ans[i] != mp(-1, -1)) {
cout << ans[i].first << ' ' << ans[i].second << '\n';
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
10112 KB |
Output is correct |
| 2 |
Correct |
15 ms |
8832 KB |
Output is correct |
| 3 |
Correct |
8 ms |
2304 KB |
Output is correct |
| 4 |
Correct |
17 ms |
8960 KB |
Output is correct |
| 5 |
Correct |
16 ms |
9216 KB |
Output is correct |
| 6 |
Correct |
7 ms |
2048 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1821 ms |
1391008 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1825 ms |
1382420 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1825 ms |
1382420 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
10112 KB |
Output is correct |
| 2 |
Correct |
15 ms |
8832 KB |
Output is correct |
| 3 |
Correct |
8 ms |
2304 KB |
Output is correct |
| 4 |
Correct |
17 ms |
8960 KB |
Output is correct |
| 5 |
Correct |
16 ms |
9216 KB |
Output is correct |
| 6 |
Correct |
7 ms |
2048 KB |
Output is correct |
| 7 |
Runtime error |
1821 ms |
1391008 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Halted |
0 ms |
0 KB |
- |
