| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 579238 | radal | Sweeping (JOI20_sweeping) | C++17 | 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 target("sse,sse2,sse4,avx2")
#pragma GCC optimize("unroll-loops,O2")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 15e6+20,mod = 1e9+7,inf = 1e9+10;
inline int mkay(int a,int b){
if (a+b >= mod) return a+b-mod;
if (a+b < 0) return a+b+mod;
return a+b;
}
inline int poww(int a,int k,int p){
if (k < 0) return 0;
int z = 1;
while (k){
if (k&1) z = 1ll*z*a%p;
a = 1ll*a*a%p;
k >>= 1;
}
return z;
}
int par[N][2]; // x y
int cnt,lc[N],rc[N],cnt_po,cur[N];
int X[N],Y[N],n,m,q;
vector<int> adj[N][2];
set<pll> st[N][2];
int getpar(int v,bool f){
if (par[v][f] == v) return v;
return par[v][f] = getpar(par[v][f],f);
}
void mg(int u,int v,bool f){
u = getpar(u,f);
v = getpar(v,f);
if (u == v) return;
if ((f && X[u] > X[v]) || (!f && Y[u] > Y[v])) swap(u,v);
par[u][f] = v;
adj[v][f].pb(u);
}
void add_po(int i,int x,int y,int v){
if (X[i]+Y[i] == n) return;
int h = n-x-y;
if (X[i] - x > h/2){
if (lc[v] == -1){
cnt++;
lc[v] = cnt;
}
add_po(i,h/2+x,y,lc[v]);
return;
}
if (Y[i] - y > (h+1)/2){
if (rc[v] == -1){
cnt++;
rc[v] = cnt;
}
add_po(i,x,y+(h+1)/2,rc[v]);
return;
}
par[i][0] = par[i][1] = i;
adj[i][0].clear();
adj[i][1].clear();
st[v][0].insert({X[i],i});
st[v][1].insert({Y[i],i});
cur[i] = v;
}
void dfs(int v,int i,vector<int>& ve,bool f){
if (cur[v] != i) return;
ve.pb(v);
for (int u : adj[v][f]) dfs(u,i,ve,f);
}
void vert(int l,int x,int y,int v){
if (l < x) return;
int h = n-x-y;
int top = n-l;
if (l >= x+(h/2)){
vector<pll> ve;
for (pll p : st[v][1]){
if (p.X > top) break;
ve.pb(p);
}
int sz = ve.size();
if (!sz){
if (lc[v] != -1) vert(l,x+h/2,y,lc[v]);
return;
}
for(pll p : ve) st[v][1].erase(p);
rep(i,0,sz-1) mg(ve[i].Y,ve[i+1].Y,1);
int u = getpar(ve[0].Y,1);
Y[u] = top;
st[v][1].insert({top,u});
if (lc[v] != -1) vert(l,x+h/2,y,lc[v]);
return;
}
vector<int> ve;
for (pll p : st[v][0]){
if (p.X > l) break;
dfs(p.Y,v,ve,0);
}
for (int u : ve){
st[v][0].erase({X[u],u});
st[v][1].erase({Y[u],u});
Y[u] = top;
X[u] = X[getpar(u,0)];
}
if (!ve.empty() && rc[v] == -1){
cnt++;
rc[v] = cnt;
}
for (int u : ve){
add_po(u,x,y+(h+1)/2,rc[v]);
}
if (rc[v] != -1) vert(l,x,y+(h+1)/2,rc[v]);
}
void horz(int l,int x,int y,int v){
if (l < y) return;
int h = n-x-y;
int top = n-l;
if (l >= y+((h+1)/2)){
vector<pll> ve;
for (pll p : st[v][0]){
if (p.X > top) break;
ve.pb(p);
}
int sz = ve.size();
if (!sz){
if (rc[v] != -1) horz(l,x,y+(h+1)/2,rc[v]);
return;
}
for(pll p : ve) st[v][0].erase(p);
rep(i,0,sz-1) mg(ve[i].Y,ve[i+1].Y,0);
int u = getpar(ve[0].Y,0);
X[u] = top;
st[v][0].insert({top,u});
if (rc[v] != -1) horz(l,x,y+(h+1)/2,rc[v]);
return;
}
vector<int> ve;
for (pll p : st[v][1]){
if (p.X > l) break;
dfs(p.Y,v,ve,1);
}
for (int u : ve){
st[v][0].erase({X[u],u});
st[v][1].erase({Y[u],u});
Y[u] = Y[getpar(u,1)];
X[u] = top;
}
if (!ve.empty() && lc[v] == -1){
cnt++;
lc[v] = cnt;
}
for (int u : ve) add_po(u,x+h/2,y,lc[v]);
if (lc[v] != -1) horz(l,x+h/2,y,lc[v]);
}
int main(){
ios :: sync_with_stdio(0); cin.tie(0);
memset(lc,-1,sizeof lc);
memset(rc,-1,sizeof rc);
cin >> n >> m >> q;
rep(i,1,m+1){
cin >> X[i] >> Y[i];
if (X[i]+Y[i] == n) continue;
add_po(i,0,0,0);
}
cnt_po = m;
rep(j,0,q){
int ty;
cin >> ty;
if(ty == 1){
int v;
cin >> v;
// debug(v);
cout << X[getpar(v,0)] << ' ' << Y[getpar(v,1)] << endl;
continue;
}
if (ty == 4){
cnt_po++;
cin >> X[cnt_po] >> Y[cnt_po];
add_po(cnt_po,0,0,0);
continue;
}
int l;
cin >> l;
if (ty == 2)
horz(l,0,0,0);
else if (ty == 3)
vert(l,0,0,0);
}
}