| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1084359 |
2024-09-06T04:11:42 Z |
phong |
Sweeping (JOI20_sweeping) |
C++17 |
|
95 ms |
43980 KB |
#include<bits/stdc++.h>
#define ll long long
const int nmax = 1e5 + 5, N = 1e5;
const ll oo = 1e18 + 5, base = 311;
const int lg = 62, tx = 26;
const ll mod = 1e9 + 7;
#define pii pair<ll, ll>
#define fi first
#define se second
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;
struct DSU{
int r[nmax], vis[nmax], dx[nmax];
vector<int> tmp, adj[nmax];
int get(int u){
tmp.push_back(u);
return r[u]? r[u] = get(r[u]) : u;
}
void init(){
for(int i= 1; i <= N; ++i) adj[i].push_back(i);
}
void Union(int u, int v){
u = get(u);v = get(v);
if(u != v){
if(adj[u].size() > adj[v].size()) swap(u, v);
for(auto p : adj[u]) adj[v].push_back(p);
r[u] = v;
}
}
void clear(){
for(auto p : tmp){
adj[p].clear();
adj[p].push_back(p);
vis[p] = 0;
dx[p] = 0;
}
tmp.clear();
}
}A, B;
pii a[nmax], ans[nmax];
struct node{
int id, x, y, idx;
};
bool inside(int l, int r,int h, int w, int x, int y){
return y <= l + h && x <= r + w;
}
int vis[nmax];
int scd = 0;
void solve(int l, int r, int N, vector<node> Q){
bool ok = 0;
for(auto p : Q) ok |= (p.id==1);
if(!ok) return;
scd++;
if(scd == 3) return;
int k = N / 2;
int h = N - k, w = k;
vector<node> Ql, Qr;
priority_queue<pii, vector<pii>, greater<pii>> xs, ys;
int xl, yl, xr, yr;
yl = l + h, xl = r;
yr = l, xr = r + w;
// cout << l + h<< ' ' << r + w << ' ' <<N<<endl;
vector<int> one;
for(int i = 1; i <= N; ++i) vis[i] = 0;
for(auto [t, x, y, id] : Q){
// if(scd==2 && t == 3) continue;
// cout << t << ' ' << x << ' ' << y << ' ' << id << endl;
if(t == 1){
// cout << id << ' ' << vis[x] << endl;
if(vis[x] == 0){
int u = A.get(x);
int v = B.get(x);
// cout << N << ' ' << l << ' ' << r << endl;
cout << id << ' ' << A.dx[u] <<' ' << B.dx[v] << endl;
ans[id] = {A.dx[u], B.dx[v]};
}
else if(vis[x] == 1){
// cout << x << ' ' << vis[x] << endl;
Ql.push_back({t, x, y, id});
}
else Qr.push_back({t, x, y, id});
}
else if(t == 2){
int L = x;
// if(L == 0 || N - L == 0) continue;
if(L >= h){
// cout << L <<' ' << h<< endl;
while(xs.size()){
pii tmp = xs.top();
if(tmp.fi <= r + N - L){
one.push_back(tmp.se);
xs.pop();
}
else{
break;
}
}
if(one.empty()) continue;
for(int i = 1; i < one.size(); ++i) A.Union(one[i - 1], one[i]);
int root = A.get(one[0]);
A.dx[root] = r + N - L;
xs.push({r + N - L, root});
one.clear();
Ql.push_back({t, L - h, 0, id});
}
else{
// cout << L << ' ' << h << endl;
while(ys.size()){
pii tmp = ys.top();
if(tmp.fi <= l + L){
int root = tmp.se;
for(auto v : B.adj[root]){
if(B.vis[v] == 1) continue;
// cout << v << ' ';
if(A.dx[A.get(v)]== r + w) continue;
Qr.push_back({4, r + w, tmp.fi, v});
B.vis[v] = 1;
vis[v] = 2;
}
ys.pop();
}
else break;
}
// cout << t << ' ' << L <<' ' << id<< endl;
Qr.push_back({t, L, 0, id});
}
}
else if(t == 3){
int L = N - x;
// if(L == 0 || N - L ==0) continue;
if(L > h){
while(xs.size()){
pii tmp = xs.top();
if(tmp.fi <= r + N - L){
int root = tmp.se;
for(auto v : A.adj[root]){
if(A.vis[v]) continue;
if(B.dx[B.get(v)]== l + h) continue;
Ql.push_back({4, tmp.fi, l + h, v});
// cout << v << ' ';
A.vis[v] = 1;
vis[v] = 1;
}
xs.pop();
}
else break;
}
Ql.push_back({t, x, 0, id});
}
else{
while(ys.size()){
pii tmp = ys.top();ys.pop();
if(tmp.fi <= l + L){
one.push_back(tmp.se);
ys.pop();
}
else break;
}
if(one.empty()) continue;
for(int i = 1; i < one.size(); ++i) B.Union(one[i - 1], one[i]);
int root = B.get(one[0]);
B.dx[root] = l + L;
ys.push({l + L, root});
one.clear();
Qr.push_back({t, x - w, 0, id});
}
}
else{
if(inside(l, r, h, w, x, y)){
xs.push({x, id});
ys.push({y, id});
A.dx[id] = x;
B.dx[id] = y;
// cout << id << endl;
}
else{
if(inside(yl, xl, k, k, x, y)){
Ql.push_back({t, x, y, id});
vis[id] = 1;
// cout << id << ' ';
}
else{
Qr.push_back({t, x, y, id});
vis[id] = 2;
// cout << id << ' ' << vis[id];
}
}
}
}
cout << endl;
A.clear();B.clear();
//// if(N == 1) return;
solve(yl, xl, N - h, Ql);
solve(yr, xr, N - w, Qr);
}
int n, m, q;
main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("code.inp", "r", stdin);
// freopen("code.out", "w", stdout);
cin >> n >> m >> q;
vector<node> Q;
for(int i = 1, x, y; i <= m; ++i){
cin >> x >> y;
Q.push_back({4, x, y, i});
a[i] = {x, y};
}
A.init(), B.init();
int scc = m;vector<int> tmp;
for(int e = 1; e <= q; ++e){
int t, p, x, y;
cin >> t;
if(t != 4){
cin >> p;
Q.push_back({t, p, 0, e});
if(t == 1)tmp.push_back(e);
}
else{
cin >> x >> y;
Q.push_back({4, x, y, ++scc});
a[scc] = {x, y};
}
}
solve(0, 0, n, Q);
// for(auto p : tmp) cout << ans[p].fi << ' ' << ans[p].se << endl;
}
/*
6 2 10
1 1
4 0
4 2 3
3 3
1 1
4 1 2
2 3
2 0
1 4
3 2
1 3
1 2
*/
Compilation message
sweeping.cpp: In function 'void solve(int, int, int, std::vector<node>)':
sweeping.cpp:102:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | for(int i = 1; i < one.size(); ++i) A.Union(one[i - 1], one[i]);
| ~~^~~~~~~~~~~~
sweeping.cpp:8:12: warning: narrowing conversion of 'tmp.std::pair<long long int, long long int>::first' from 'long long int' to 'int' [-Wnarrowing]
8 | #define fi first
| ^
sweeping.cpp:119:57: note: in expansion of macro 'fi'
119 | Qr.push_back({4, r + w, tmp.fi, v});
| ^~
sweeping.cpp:8:12: warning: narrowing conversion of 'tmp.std::pair<long long int, long long int>::first' from 'long long int' to 'int' [-Wnarrowing]
8 | #define fi first
| ^
sweeping.cpp:142:50: note: in expansion of macro 'fi'
142 | Ql.push_back({4, tmp.fi, l + h, v});
| ^~
sweeping.cpp:163:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
163 | for(int i = 1; i < one.size(); ++i) B.Union(one[i - 1], one[i]);
| ~~^~~~~~~~~~~~
sweeping.cpp: At global scope:
sweeping.cpp:200:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
200 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
30 ms |
35420 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
88 ms |
43980 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
95 ms |
43952 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
95 ms |
43952 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
30 ms |
35420 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
