| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 925723 | manizare | Sweeping (JOI20_sweeping) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 int long long
#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 = 2e6 + 10 , maxp = 4000, lg = 22 , mod = 998244353 , sq =700 , inf = 1e18 ;
int n,m,q,x[maxn] ,y[maxn] ,px[maxn] , py[maxn] , cnt = 2 ;
vector <int> gx[maxn],gy[maxn] ;
int fx(int v){
return (px[v]==0 ? v : px[v]=fx(px[v]));
}
int fy(int v){
return (py[v]==0 ? v : py[v]=fy(py[v]));
}
void mx(int v,int u){
u = fx(u) ; v = fx(v);
if(v==u)return ;
px[v]= u ;
gx[u].pb(v);
}
void my(int v,int u){
u = fy(u) ; v = fy(v);
if(v==u)return ;
py[v]= u ;
gy[u].pb(v);
}
void reval(int v){
x[v] = x[fx(v)];
y[v] = y[fy(v)];
}
vector <int> rem ;
void dfsy(int v,int r){
rem.pb(v);
for(int u :gy[v]){
if(fy(u)!=r)continue ;
dfsy(u,r) ;
}
}
struct rec{
set <pii> sx , sy ;
int X , Y , d , cl , cr ;
void add(int v){
px[v] = py[v] = 0 ;
gx[v].clear() ;gy[v].clear();
sx.insert({y[v] , v}) ;
sy.insert({x[v] , v}) ;
}
void ers(int v){
if(fx(v) == v){
sx.erase({y[v] , v}) ;
}
if(fy(v) == v){
sy.erase({x[v] , v});
}
}
void upx(int l){
if(l < X)return ;
if(l <= X+d){
rem.clear() ;
while(sz(sy) && (*sy.begin()).F <= l){
int v = (*sy.begin()).S ;
dfsy(v,v) ;
sy.erase(sy.begin()) ;
}
for(int id : rem){
reval(id) ;
ers(id);
}
}else{
int maxi = n-l ;
vector <pii> az;
while(sz(sx) && (*sx.begin()).F <= maxi){
int id = (*sx.begin()).S;
az.pb({x[id] , id});
sx.erase(sx.begin()) ;
}
if(sz(az)==0)return ;
sort(all(az));
y[az.back().S] = maxi ;
sx.insert({maxi,az.back().S}) ;
rep(i , 0, sz(az)-2){
mx(az[i].S , az[i+1].S);
}
}
}
};
rec r[33*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 ;
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]){
if(r[p].cr == 0){
r[p].cr = cnt ; cnt++;
}
ADD(id , r[p].cr , m1 , Y , d/2);
}else{
if(r[p].cl == 0){
r[p].cl = cnt ; cnt ++ ;
}
ADD(id , r[p].cl, X , m2 , d/2) ;
}
}
void updx(int l , int p = 1,int X= 0 , int Y= 0, int d= n){
r[p].X = X ; r[p].Y = Y ; r[p].d = d ;
if(d==0)return ;
if(X > l)return ;
int m1 = X+(d+1)/2 , m2 = Y+(d+1)/2 ;
r[p].upx(l);
if(l <= X+d){
if(r[p].cl == 0){
r[p].cl = cnt ; cnt++;
}
while(sz(rem)){
int v = rem.back() ;
r[r[p].cl].add(v);
rem.pop_back() ;
}
updx(l ,r[p].cl, X , m2 , d/2);
return ;
}
updx(l , r[p].cr , m1 , Y , d/2);
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m >> q ;
int id = 1;
r[1].X = 0 ; r[1].Y = 0 ; r[1].d = n ;
rep(i , 1 ,m){
cin >> x[id]>> y[id];
ADD(id);
id++;
}
rep(i ,1 , q){
int t ;
cin >> t ;
if(t==1){
int k ;
cin >> k ;
reval(k);
cout << x[k] << " "<< y[k] << "\n";
}
if(t==4){
cin >> x[id] >> y[id] ;
ADD(id);
id++;
}
if(t==2){
int l ;
cin >> l ;
updx(l) ;
}
}
return 0;
}
/*
*/