Submission #926045

#TimeUsernameProblemLanguageResultExecution timeMemory
926045manizareSweeping (JOI20_sweeping)C++14
10 / 100
8768 ms2096660 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...