#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld double
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define pb emplace_back
#define X first
#define Y second
const int N = 1500005;
typedef pair<int,int> ii;
typedef vector<int> vi;
struct DSU {
vector<int> val;
vector<vi> vec;
int par[N];
void init() {
val.clear();
vec.clear();
}
int add(int x,int v) {
int idx = sz(val);
val.push_back(x);
vec.push_back({});
if (v >= 0) {
par[v] = idx;
vec.back().pb(v);
}
return idx;
}
int join(int x,int y) {
if (sz(vec[x]) < sz(vec[y]))
swap(x,y);
val[x] = max(val[x],val[y]);
for(int u : vec[y])
par[u] = x,
vec[x].pb(u);
return x;
}
} fX, fY;
typedef array<int,3> ar;
ii ans[N];
ii pos[N];
int n, m, q;
bool done[N];
void getReal(int i) {
pos[i].X = fX.val[fX.par[i]];
pos[i].Y = fY.val[fY.par[i]];
}
void calc(int x,int y,vector<ar> vec) {
if (vec.empty())
return;
int dif = n - x - y;
if (dif == 0) {
for(ar a : vec)
if (a[0] == 1)
ans[a[2]].X = x,
ans[a[2]].Y = y;
return;
}
fX.init();
fY.init();
int X = x + (dif + 1) / 2;
int Y = y + (dif + 2) / 2;
vector<ar> vecU;
vector<ar> vecR;
multiset<ii> Sx;
multiset<ii> Sy;
for(ar a : vec) {
if (a[0] == 1) {
int i = a[1];
if (pos[i].Y >= Y) { vecU.pb(a); continue; }
if (pos[i].X >= X) { vecR.pb(a); continue; }
ans[i].X = fX.val[fX.par[i]];
ans[i].Y = fY.val[fY.par[i]];
}
if (a[0] == 2) {
if (a[1] >= Y) {
int nxt = n - a[1];
int idx = fX.add(nxt,-1);
while (Sx.size() && (*Sx.begin()).X <= nxt) {
int x = (*Sx.begin()).Y;
Sx.erase( Sx.begin());
idx = fX.join(idx,x);
}
Sx.insert(ii(fX.val[idx],idx));
vecU.pb(a);
}
else {
while (Sy.size() && (*Sy.begin()).X <= a[1]) {
int x = (*Sy.begin()).Y;
Sy.erase( Sy.begin());
for(int u : fY.vec[x])
if(!done[u]) {
done[u] = 1;
getReal(u);
pos[u].X = n - a[1];
vecR.push_back({4,u,0});
}
}
vecR.pb(a);
}
}
if (a[0] == 3) {
if (a[1] >= X) {
int nxt = n - a[1];
int idx = fY.add(nxt,-1);
while (Sy.size() && (*Sy.begin()).X <= nxt) {
int x = (*Sy.begin()).Y;
Sy.erase( Sy.begin());
idx = fY.join(idx,x);
}
Sy.insert(ii(fY.val[idx],idx));
vecR.pb(a);
}
else {
while (Sx.size() && (*Sx.begin()).X <= a[1]) {
int x = (*Sx.begin()).Y;
Sx.erase( Sx.begin());
for(int u : fX.vec[x])
if(!done[u]) {
done[u] = 1;
getReal(u);
pos[u].Y = n - a[1];
vecU.push_back({4,u,0});
}
}
vecU.pb(a);
}
}
if (a[0] == 4) {
int i = a[1];
done[i] = 0;
if (pos[i].Y >= Y) { done[i] = 1; vecU.pb(a); continue; }
if (pos[i].X >= X) { done[i] = 1; vecR.pb(a); continue; }
int xv = fX.add(pos[i].X,i);
int yv = fY.add(pos[i].Y,i);
Sx.insert(ii(fX.val[xv],xv));
Sy.insert(ii(fY.val[yv],yv));
}
}
calc(x,Y,vecU);
calc(X,y,vecR);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m >> q;
vector<ar> Que;
int tot = 0;
for(int i = 0 ; i < m ; ++i) {
int x; cin >> x;
int y; cin >> y;
pos[++tot] = ii(x,y);
Que.push_back({4,tot,0});
}
for(int i = 0 ; i < q ; ++i) {
ans[i] = ii(-1,-1);
int t; cin >> t;
if (t < 4) {
int x; cin >> x;
Que.push_back({t,x,i});
}
else {
int x; cin >> x;
int y; cin >> y;
pos[++tot] = ii(x,y);
Que.push_back({4,tot,i});
}
}
calc(0,0,Que);
for(int i = 0 ; i < q ; ++i)
if (ans[i].X >= 0)
cout << ans[i].X << " ",
cout << ans[i].Y << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
1408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3833 ms |
124456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4118 ms |
145092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4118 ms |
145092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
1408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
