#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
const int N = 2e6 + 5;
struct Q {
int t, x, y, z;
};
struct DSU {
int val[N], a[N];
vector<int> v[N];
int find_set(int x) {
return a[x] < 0 ? x : a[x];
}
int get_val(int x) {
return val[find_set(x)];
}
void reset(int x, int y) {
a[x] = -1;
val[x] = y;
v[x] = {x};
}
void mrg(int x, int y) {
x = find_set(x);
y = find_set(y);
if (x == y)
return;
if (v[x].size() < v[y].size()) {
swap(x, y);
swap(val[x], val[y]);
}
for (const int &el : v[y]) {
v[x].push_back(el);
a[el] = x;
}
v[y].clear();
}
void set_val(int x, int y) {
x = find_set(x);
val[x] = y;
}
} dsu_x, dsu_y;
pair<int, int> ans[N];
bool send_to_up[N], send_to_right[N];
vector<int> selected;
void get_not_gr_than_x(priority_queue<pair<int, int>,
vector<pair<int, int>>,
greater<pair<int, int>>> &pq, int x) {
selected.clear();
while (!pq.empty() && pq.top().first <= x) {
selected.push_back(pq.top().second);
pq.pop();
}
}
void upd_pq(priority_queue<pair<int, int>,
vector<pair<int, int>>,
greater<pair<int, int>>> &pq, DSU &dsu, int x) {
get_not_gr_than_x(pq, x);
if (!selected.empty()) {
for (const int &y : selected) {
dsu.mrg(y, selected[0]);
}
dsu.set_val(selected[0], x);
pq.push({x, dsu.find_set(selected[0])});
}
}
priority_queue<pair<int, int>,
vector<pair<int, int>>,
greater<pair<int, int>>> pq_x, pq_y;
void solve(int offset_x, int offset_y, int n, vector<Q> qrs) {
if (qrs.empty())
return;
while (!pq_x.empty())
pq_x.pop();
while (!pq_y.empty())
pq_y.pop();
// cout << n << " " << offset_x << " " << offset_y << "\n";
// for (Q q : qrs) {
// cout << q.t << " " << q.x << " " << q.y << " " << q.z << "\n";
// }
// cout << "\n";
vector<Q> up_qrs, rt_qrs;
int sq_side = (n + 1) / 2;
for (const Q &c : qrs) {
if (c.t == 1) {
if (send_to_up[c.x]) {
up_qrs.push_back(c);
}
else if (send_to_right[c.x]) {
rt_qrs.push_back(c);
}
else {
ans[c.y] = {dsu_x.get_val(c.x) + offset_x,
dsu_y.get_val(c.x) + offset_y};
}
}
else if (c.t == 2) {
if (c.x < sq_side) {
rt_qrs.push_back(c);
get_not_gr_than_x(pq_y, c.x);
for (const int &gr : selected) {
for (const int &el : dsu_y.v[gr]) {
if (!send_to_right[el] && !send_to_up[el]) {
Q new_q;
new_q.t = 4;
new_q.x = dsu_x.get_val(el);
new_q.y = dsu_y.get_val(el);
send_to_right[el] = true;
new_q.x = max(new_q.x, n - c.x);
new_q.x -= sq_side;
new_q.z = el;
rt_qrs.push_back(new_q);
}
}
}
}
else {
upd_pq(pq_x, dsu_x, n - c.x);
up_qrs.push_back(c);
up_qrs.back().x = c.x - sq_side;
}
}
else if (c.t == 3) {
if (c.x < sq_side) {
up_qrs.push_back(c);
get_not_gr_than_x(pq_x, c.x);
for (const int &gr : selected) {
for (const int &el : dsu_x.v[gr]) {
if (!send_to_right[el] && !send_to_up[el]) {
Q new_q;
new_q.t = 4;
new_q.x = dsu_x.get_val(el);
new_q.y = dsu_y.get_val(el);
send_to_up[el] = true;
new_q.y = max(new_q.y, n - c.x);
new_q.y -= sq_side;
new_q.z = el;
up_qrs.push_back(new_q);
}
}
}
}
else {
upd_pq(pq_y, dsu_y, n - c.x);
rt_qrs.push_back(c);
rt_qrs.back().x = c.x - sq_side;
}
}
else {
if (c.x > sq_side) {
rt_qrs.push_back(c);
rt_qrs.back().x -= sq_side;
send_to_right[c.z] = true;
}
else if (c.y > sq_side) {
up_qrs.push_back(c);
up_qrs.back().y -= sq_side;
send_to_up[c.z] = true;
}
else {
send_to_up[c.z] = false;
send_to_right[c.z] = false;
dsu_x.reset(c.z, c.x);
dsu_y.reset(c.z, c.y);
pq_x.push({c.x, c.z});
pq_y.push({c.y, c.z});
}
}
}
if (n != 0) {
solve(offset_x, offset_y + sq_side, n - sq_side, up_qrs);
solve(offset_x + sq_side, offset_y, n - sq_side, rt_qrs);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m, q, z = 0;
cin >> n >> m >> q;
vector<Q> qrs;
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
qrs.push_back({4, x, y, z++});
}
int ask_qr_ct = 0;
for (int i = 0; i < q; i++) {
Q new_q;
cin >> new_q.t >> new_q.x;
if (new_q.t == 1) {
new_q.x--;
new_q.y = ask_qr_ct++;
}
else if (new_q.t == 4) {
cin >> new_q.y;
new_q.z = z++;
}
qrs.push_back(new_q);
}
solve(0, 0, n, qrs);
for (int i = 0; i < ask_qr_ct; i++) {
cout << ans[i].first << " " << ans[i].second << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
68 ms |
97400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3412 ms |
445224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2876 ms |
402628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2876 ms |
402628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
68 ms |
97400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
