| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1084821 |
2024-09-07T04:33:33 Z |
phong |
Sweeping (JOI20_sweeping) |
C++17 |
|
103 ms |
43948 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);
adj[u].clear();
r[u] = v;
}
}
void clear(){
for(auto p : tmp){
adj[p].clear();
adj[p].push_back(p);
dx[p] = 0;
r[p] = 0;
vis[p] = 0;
}
// for(int i = 1; i <= 1e5; ++i) vis[i]= 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 l <= y && y <= l + h && x <= r + w && r <= x;
}
int vis[nmax];
int scd = 0;
/*
4 3 2
4 0
1 2
3 0
3 3
1 3
*/
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;
// if(N == 0) 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;
if(N == 1) h = 1, w = 1;
vector<int> one;
for(int i = 1; i <= 1e5; ++i) vis[i] = 0;
for(auto [t, x, y, id] : Q){
if(t == 1){
if(vis[x] == 0){
int u = A.get(x);
int v = B.get(x);
ans[id] = {A.dx[u], B.dx[v]};
}
else{
if(vis[x] == 1){
Ql.push_back({t, x, y, id});
}
else{
Qr.push_back({t, x, y, id});
}
}
}
else if(t == 2){
int L = x;
if(L >= h || N == 1){
while(xs.size()){
pii tmp = xs.top();
if(tmp.fi <= r + N - L){
one.push_back(tmp.se);
xs.pop();
}
else{
break;
}
}
Ql.push_back({t, L - h, 0, id});
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();
}
else{
// if(N == 1)cout << "?";
// 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;
Qr.push_back({4, r + w, tmp.fi, v});
B.vis[v] = 1;
B.tmp.push_back(v);
vis[v] = 2;
}
ys.pop();
}
else break;
}
Qr.push_back({t, L, 0, id});
}
}
else if(t == 3){
int L = N - x;
if(L > h && N != 1){
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;
Ql.push_back({4, tmp.fi, l + h, v});
A.vis[v] = 1;
A.tmp.push_back(v);
vis[v] = 1;
}
xs.pop();
}
else break;
}
Ql.push_back({t, x, 0, id});
}
else{
while(ys.size()){
pii tmp = ys.top();
if(tmp.fi <= l + L){
one.push_back(tmp.se);
ys.pop();
}
else break;
}
Qr.push_back({t, x - w, 0, id});
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();
}
}
else{
// cout << l << ' ' << r << ' ' << h << ' ' << w << ' ' << x << ' ' << y << endl;
if(inside(l, r, h, w, x, y) || N == 1){
xs.push({x, id});
ys.push({y, id});
A.dx[id] = x;
B.dx[id] = y;
}
else{
if(inside(yl, xl, k, k, x, y)){
Ql.push_back({t, x, y, id});
vis[id] = 1;
}
else{
Qr.push_back({t, x, y, id});
vis[id] = 2;
}
}
// if(N == 1) return;
}
}
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;
}
/*
4 3 2
4 0
1 2
3 0
3 3
1 3
*/
Compilation message
sweeping.cpp: In function 'void solve(int, int, int, std::vector<node>)':
sweeping.cpp:107:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | 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:125:57: note: in expansion of macro 'fi'
125 | 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:146:50: note: in expansion of macro 'fi'
146 | Ql.push_back({4, tmp.fi, l + h, v});
| ^~
sweeping.cpp:168:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
168 | for(int i = 1; i < one.size(); ++i) B.Union(one[i - 1], one[i]);
| ~~^~~~~~~~~~~~
sweeping.cpp: At global scope:
sweeping.cpp:202:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
202 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
12888 KB |
Output is correct |
| 2 |
Incorrect |
22 ms |
12632 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
90 ms |
43852 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
103 ms |
43948 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
103 ms |
43948 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
12888 KB |
Output is correct |
| 2 |
Incorrect |
22 ms |
12632 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
