#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second
#define ld long double
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= (b);i++)
#define per(i , a , b) for(int i=a;i >= (b);i--)
#define deb(x) cout <<#x << " : " << x << "\n" ;
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 16e6 + 10 , maxp = 2e6 + 10, lg = 22 , mod = 998244353 , sq =700 , inf = 1e9 ;
int n,m,q,x[maxp] ,y[maxp] ,p[2][maxp] , cnt = 2 , c = 2 ;
vector <int> cm ;
vector <int> g[2][maxp] ;
int f(int v,int t){
return (p[t][v]==0 ? v : p[t][v]=f(p[t][v],t));
}
void mrg(int v,int u , int t){
u = f(u,t) ; v = f(v,t);
if(v==u)return ;
p[t][v]= u ;
g[t][u].pb(v);
}
void reval(int v){
x[v] = x[f(v,0)];
y[v] = y[f(v,1)];
}
vector <int> rem ;
void dfs(int v,int r,int t) {
rem.pb(v);
for(int u :g[t][v]){
if(f(u,t)!=r)continue ;
dfs(u,r,t) ;
}
}
struct rec{
set <pii> s[2] ;
int X , Y , d , cl , cr ;
void add(int v){
p[0][v] = p[1][v] = 0 ;
g[0][v].clear() ;g[1][v].clear();
s[0].insert({y[v] , v}) ;
s[1].insert({x[v] , v}) ;
}
void ers(int v){
if(f(v,0) == v){
s[0].erase({y[v] , v}) ;
}
if(f(v,1) == v){
s[1].erase({x[v] , v});
}
}
void up1(int l ,int t){
rem.clear() ;
while(sz(s[!t]) && (*s[!t].begin()).F <= l){
int v = (*s[!t].begin()).S ;
dfs(v,v,!t) ;
s[!t].erase(s[!t].begin()) ;
}
for(int id : rem){
reval(id) ;
}
for(int id : rem){
ers(id) ;
}
for(int id : rem){
if(t == 0){
y[id] = n-l ;
}else{
x[id] = n-l ;
}
}
}
void up2(int l,int t){
int maxi = n-l ;
vector <pii> az;
while(sz(s[t]) && (*s[t].begin()).F <= maxi){
int id = (*s[t].begin()).S;
if(t==0){
reval(id);
az.pb({x[id] , id});
}else{
reval(id);
az.pb({y[id] , id}) ;
}
s[t].erase(s[t].begin()) ;
}
if(sz(az)==0)return ;
sort(all(az));
if(t==0){
y[az.back().S] = maxi ;
}else{
x[az.back().S] = maxi ;
}
s[t].insert({maxi,az.back().S}) ;
rep(i , 0, sz(az)-2){
mrg(az[i].S , az[i+1].S , !t);
}
}
};
rec r[maxn] ;
void ADD(int id , int p = 1 , int X = 0 , int Y = 0 , int d =n){
r[p].X = X ; r[p].Y = Y ; r[p].d = (d+1)/2 ;
if(r[p].cl ==0 ){
r[p].cl = c ; c++;
}
if(r[p].cr ==0){
r[p].cr = c ; c++ ;
}
int m1 = X+(d+1)/2 , m2 = Y+(d+1)/2 ;
if(d==0){
r[p].add(id) ;
return ;
}
if(m1 > x[id] && m2 > y[id]){
r[p].add(id) ;
return ;
}
if(m1 <= x[id]){
ADD(id , r[p].cr , m1 , Y , d/2);
}else{
ADD(id , r[p].cl , X , m2 , d/2) ;
}
}
void upd(int l , int t , int p = 1,int X= 0 , int Y= 0, int d= n){
r[p].X = X ; r[p].Y = Y ; r[p].d = (d+1)/2 ;
if(r[p].cl ==0 ){
r[p].cl = c ; c++;
}
if(r[p].cr ==0){
r[p].cr = c ; c++ ;
}
if(d==0)return ;
if((t==0 && X > l) || (t==1 && Y > l))return ;
int m1 = X+(d+1)/2 , m2 = Y+(d+1)/2 ;
if((t==0&& l+(d&1)<=m1) || (t==1&& l+(d&1)<=m2)){
r[p].up1(l,t);
while(sz(rem)){
int v = rem.back() ;
ADD(v);
rem.pop_back() ;
}
if(t==0)upd(l , t ,r[p].cl , X , m2 , d/2);
else upd(l,t, r[p].cr , m1 , Y , d/2) ;
}
if((t==0&&l >= m1) || (t==1&&l >= m2)){
r[p].up2(l,t);
if(t==0)upd(l, t , r[p].cr , m1 , Y , d/2);
else upd(l,t , r[p].cl , X , m2 , d/2) ;
}
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m >> q ;
int id = 1;
rep(i , 1 , m){
cin >> x[id] >> y[id] ;
ADD(id) ;
id++;
}
while(q--){
int t ;
cin >> t ;
if(t==1){
int a ;cin >> a;
reval(a);
cout << x[a] << " " << y[a] << "\n" ;
}
if(t==3){
int l ;
cin >> l ;
upd(l , 0);
}
if(t==2){
int l ;
cin >> l ;
upd(l , 1);
}
if(t==4){
cin >> x[id] >> y[id];
ADD(id) ;
id++;
}
}
return 0;
}
/*
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
942 ms |
1975112 KB |
Output is correct |
| 2 |
Incorrect |
882 ms |
1974680 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4197 ms |
2080296 KB |
Output is correct |
| 2 |
Correct |
4030 ms |
2078500 KB |
Output is correct |
| 3 |
Correct |
4054 ms |
2078340 KB |
Output is correct |
| 4 |
Correct |
3425 ms |
2065064 KB |
Output is correct |
| 5 |
Correct |
8768 ms |
2096660 KB |
Output is correct |
| 6 |
Correct |
6928 ms |
2084860 KB |
Output is correct |
| 7 |
Correct |
4066 ms |
2076692 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2804 ms |
2053340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2804 ms |
2053340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
942 ms |
1975112 KB |
Output is correct |
| 2 |
Incorrect |
882 ms |
1974680 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
