| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 579250 |
2022-06-18T15:57:04 Z |
radal |
Sweeping (JOI20_sweeping) |
C++17 |
|
8462 ms |
441128 KB |
#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 = 2e6+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){
par[i][0] = i;
par[i][1] = i;
adj[i][0].clear();
adj[i][1].clear();
cur[i] = -1;
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];
par[i][0] = i;
par[i][1] = 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;
cout << X[getpar(v,0)] << ' ' << Y[getpar(v,1)] << endl;
continue;
}
if (ty == 4){
cnt_po++;
cin >> X[cnt_po] >> Y[cnt_po];
rep(i,0,2) par[cnt_po][i] = 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);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
171 ms |
298060 KB |
Output is correct |
| 2 |
Incorrect |
158 ms |
297884 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4253 ms |
383140 KB |
Output is correct |
| 2 |
Correct |
3889 ms |
382048 KB |
Output is correct |
| 3 |
Correct |
3994 ms |
382320 KB |
Output is correct |
| 4 |
Correct |
3116 ms |
370188 KB |
Output is correct |
| 5 |
Correct |
8462 ms |
396252 KB |
Output is correct |
| 6 |
Correct |
6834 ms |
386224 KB |
Output is correct |
| 7 |
Correct |
3866 ms |
380736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3962 ms |
388832 KB |
Output is correct |
| 2 |
Correct |
4789 ms |
404152 KB |
Output is correct |
| 3 |
Correct |
1412 ms |
383260 KB |
Output is correct |
| 4 |
Correct |
5610 ms |
441128 KB |
Output is correct |
| 5 |
Correct |
4553 ms |
411644 KB |
Output is correct |
| 6 |
Correct |
2841 ms |
406660 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3962 ms |
388832 KB |
Output is correct |
| 2 |
Correct |
4789 ms |
404152 KB |
Output is correct |
| 3 |
Correct |
1412 ms |
383260 KB |
Output is correct |
| 4 |
Correct |
5610 ms |
441128 KB |
Output is correct |
| 5 |
Correct |
4553 ms |
411644 KB |
Output is correct |
| 6 |
Correct |
2841 ms |
406660 KB |
Output is correct |
| 7 |
Correct |
4000 ms |
393896 KB |
Output is correct |
| 8 |
Correct |
3962 ms |
395184 KB |
Output is correct |
| 9 |
Correct |
3973 ms |
393068 KB |
Output is correct |
| 10 |
Correct |
2877 ms |
383236 KB |
Output is correct |
| 11 |
Correct |
6611 ms |
415648 KB |
Output is correct |
| 12 |
Correct |
7274 ms |
410600 KB |
Output is correct |
| 13 |
Correct |
6991 ms |
432300 KB |
Output is correct |
| 14 |
Correct |
303 ms |
301620 KB |
Output is correct |
| 15 |
Correct |
1839 ms |
380256 KB |
Output is correct |
| 16 |
Correct |
3612 ms |
388672 KB |
Output is correct |
| 17 |
Correct |
3753 ms |
395448 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
171 ms |
298060 KB |
Output is correct |
| 2 |
Incorrect |
158 ms |
297884 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
