// Zende bad Shoma nasime faghat !
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
//#define int long long
using namespace std;
const int N = 15e5 + 10;
const int SGN = 45e5 + 2;
int lc[SGN], rc[SGN], la = 0;
vector<int> GX[N], GY[N];
int parX[N], parY[N], X[N], Y[N], wh[N], lapo = 0;
int FindX(int u){ return parX[u] = (parX[u] == u ? u : FindX(parX[u])); }
int FindY(int u){ return parY[u] = (parY[u] == u ? u : FindY(parY[u])); }
int GetX(int u){ return X[FindX(u)]; }
int GetY(int u){ return Y[FindY(u)]; }
void UniteX(int u, int v){
//cerr << "# " << u << ' ' << v << '\n';
u = FindX(u); v = FindX(v);
if(u == v) return ;
if(pair<int, int>(GetY(u), u) < pair<int, int>(GetY(v), v)) swap(u, v);
parX[v] = u;
GX[u].pb(v);
}
/*
void UniteY(int u, int v){
u = FindY(u); v = FindY(v);
if(u == v) return ;
if(GetX(u) < GetX(v)) swap(u, v);
parY[v] = u;
GY[u].pb(v);
}
*/
struct CMPX {
bool operator ()(int i, int j) const {
if(GetX(i) != GetX(j))
return GetX(i) < GetX(j);
return i < j;
}
};
struct CMPY {
bool operator ()(int i, int j) const {
if(GetY(i) != GetY(j))
return GetY(i) < GetY(j);
return i < j;
}
};
set<int, CMPX> stX[SGN];
set<int, CMPY> stY[SGN];
int n, m, Q;
vector<int> vis;
void DFSY(int u, int id){
if(wh[u] != id) return ;
assert(GY[u].empty());
vis.pb(u);
for(auto adj : GY[u])
DFSY(adj, id);
}
void Ins(int id, int po, int X0, int Y0){
assert(id < SGN);
int L = n - (X0 + Y0);
int X1 = X0 + (L / 2);
int Y1 = Y0 + ((L + 1) / 2);
if(X[po] > X1){
if(lc[id] == 0) lc[id] = ++la;
Ins(lc[id], po, X1, Y0);
} else if(Y[po] > Y1){
if(rc[id] == 0) rc[id] = ++la;
Ins(rc[id], po, X0, Y1);
} else {
//cerr << "ins: " << po << ' ' << id << '\n';
wh[po] = id;
parX[po] = po; parY[po] = po;
stX[id].insert(po); stY[id].insert(po);
GX[po].clear(); GY[po].clear();
}
}
vector<int> Un;
void H(int id, int l, int X0, int Y0){
if(l <= 0) return ;
//if(id == 3) debug(l);
//cerr << "H: " << id << ' ' << l << ' ' << X0 << ' ' << Y0 << '\n';
int L = n - (X0 + Y0);
int X1 = X0 + (L / 2);
int Y1 = Y0 + ((L + 1) / 2);
int rt, mv = L - l;
assert(L > 1);
//if(l == L) return ;
//assert(l <= L);
if(Y1 - Y0 <= l){ // shift
//cerr << "! " << mv << ' ' << X0 << ' ' << Y0 << ' ' << '\n' << '\n';
Un.clear();
//cerr << "list: ";
//for(auto po : stX[id]) cerr << po << ' ';
//cerr << '\n';
for(auto po : stX[id]){
if(GetX(po) > X0 + mv) break;
Un.pb(po);
//cerr << "% " << po << '\n';
}
for(auto u : Un) stX[id].erase(u);
for(int i = 0; i + 1 < (int) Un.size(); i++) UniteX(Un[i], Un[i + 1]);
if(!Un.empty()){
rt = FindX(Un.back());
X[rt] = X0 + mv;
stX[id].insert(rt);
}
for(auto u : Un){
assert(GetX(u) == X0 + mv);
}
/*
for(auto u : Un){
X[u] = X0 + mv;
stX[id].insert(u);
}
*/
if(rc[id] != 0)
H(rc[id], l - (Y1 - Y0), X0, Y1);
} else { // remove
vis.clear();
for(auto po : stY[id]){
if(GetY(po) > Y0 + l) break;
DFSY(po, id);
//vis.pb(po);
}
//cerr << "vis: ";
//for(auto x : vis) cerr << x << '\n';
//cerr << '\n';
for(auto u : vis) stY[id].erase(u), stX[id].erase(u);
for(auto u : vis) X[u] = X0 + mv, Y[u] = GetY(u);
assert(X0 + mv > X1);
if(!vis.empty()){
for(auto u : vis)
Ins(0, u, 0, 0);
}
if(lc[id] != 0)
H(lc[id], l, X1, Y0);
}
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m >> Q;
for(int i = 0; i < m; i++){
lapo ++;
cin >> X[lapo] >> Y[lapo];
Ins(0, lapo, 0, 0);
}
//cerr << '\n';
int type, Li, Pi;
for(int i = 1; i <= Q; i++){
if(i % 1000 == 0) debug(i);
cin >> type;
assert(type != 3);
if(type == 4){
lapo ++;
cin >> X[lapo] >> Y[lapo];
Ins(0, lapo, 0, 0);
}
if(type == 2){
cin >> Li;
H(0, Li, 0, 0);
/*for(int j = 1; j <= lapo; j++)
if(GetY(j) <= Li)
X[j] = max(X[j], n - Li);
*/
}
if(type == 1){
cin >> Pi;
cout << GetX(Pi) << ' ' << GetY(Pi) << '\n';
}
}
//cerr << wh[2] << ' ' << lc[lc[ lc[0] ] ] << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
838 ms |
990412 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 |
6394 ms |
592036 KB |
Output is correct |
| 2 |
Correct |
6143 ms |
590668 KB |
Output is correct |
| 3 |
Correct |
6168 ms |
590800 KB |
Output is correct |
| 4 |
Incorrect |
5058 ms |
583064 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1324 ms |
1057912 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 |
1324 ms |
1057912 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 |
838 ms |
990412 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
