oj.uz

Submission #1084948

# Submission time Handle Problem Language Result Execution time Memory
1084948 2024-09-07T08:58:49 Z phong Sweeping (JOI20_sweeping) C++17
100 / 100
 3984 ms 640828 KB 
#include<bits/stdc++.h>
#define ll long long
const int nmax = 1e6 + 5, N = 1e6;
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
*/
vector<int> lol;
void add(int u, int id){
    vis[u] = id;
    lol.push_back(u);
}
void Del(){
    for(auto p : lol) vis[p] = 0;
    lol.clear();
}
pii dx[5];
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;
    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){
        vector<int> AA, BB, CC;
        dx[0] = {r, l};
        dx[1] = {r + 1, l};
        dx[2] = {r, l + 1};
        Del();
        for(auto [t, x, y, id] : Q){
            if(t == 1){
                int val = vis[x];
                ans[id] = dx[val];
            }
            else if(t == 2){
                if(x == 0){
                    while(BB.size()){
                        int it = BB.back();
                        CC.push_back(it);
                        BB.pop_back();
                        add(it, 1);
                    }
                }
            }
            else if(t == 3){
                int L = 1 - x;
                if(L == 1){
                    while(BB.size()){
                        int it = BB.back();
                        AA.push_back(it);
                        BB.pop_back();
                        add(it, 2);
                    }
                }
            }
            else if(t == 4){
                pii tx = {x, y};
//                cout << tx.fi << ' ' << tx.se << ' ' << id << endl;
                if(tx == dx[0]) BB.push_back(id), add(id, 0);
                else if(tx == dx[1]) CC.push_back(id), add(id, 1);
                else AA.push_back(id), add(id, 2);
            }
        }

        return;
    }
//    cout<<endl;
    vector<int> one;
    Del();
    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){
                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{
                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 || A.vis[v] == 1) continue;
                            Qr.push_back({4, r + w, tmp.fi, v});
                            B.vis[v] = 1;
                            B.tmp.push_back(v);
                            add(v, 2);
                        }
                        ys.pop();
                    }
                    else break;
                }
                Qr.push_back({t, L, 0, id});
            }
        }
        else if(t == 3){
            int L = N - x;
            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(B.vis[v] == 1 || A.vis[v] == 1) continue;
                            Ql.push_back({4, tmp.fi, l + h, v});
                            A.vis[v] = 1;
                            A.tmp.push_back(v);
                            add(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{
            if(inside(l, r, h, w, x, y)){
                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});
                    add(id, 1);
                }
                else{
                    Qr.push_back({t, x, y, id});
                    add(id, 2);
                }
            }
        }
    }
    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:159:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |                 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:172:57: note: in expansion of macro 'fi'
  172 |                             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:194:50: note: in expansion of macro 'fi'
  194 |                             Ql.push_back({4, tmp.fi, l + h, v});
      |                                                  ^~
sweeping.cpp:216:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  216 |                 for(int i = 1; i < one.size(); ++i) B.Union(one[i - 1], one[i]);
      |                                ~~^~~~~~~~~~~~
sweeping.cpp: At global scope:
sweeping.cpp:248:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  248 | main(){
      | ^~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 111324 KB Output is correct
2 Correct 111 ms 110676 KB Output is correct
3 Correct 121 ms 110648 KB Output is correct
4 Correct 122 ms 111204 KB Output is correct
5 Correct 128 ms 110932 KB Output is correct
6 Correct 94 ms 110416 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2541 ms 302028 KB Output is correct
2 Correct 2597 ms 322876 KB Output is correct
3 Correct 2561 ms 321488 KB Output is correct
4 Correct 3615 ms 430688 KB Output is correct
5 Correct 3646 ms 366200 KB Output is correct
6 Correct 3984 ms 392564 KB Output is correct
7 Correct 2537 ms 322108 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1932 ms 340464 KB Output is correct
2 Correct 1963 ms 384572 KB Output is correct
3 Correct 2102 ms 420152 KB Output is correct
4 Correct 2210 ms 551496 KB Output is correct
5 Correct 2295 ms 461816 KB Output is correct
6 Correct 1967 ms 370692 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1932 ms 340464 KB Output is correct
2 Correct 1963 ms 384572 KB Output is correct
3 Correct 2102 ms 420152 KB Output is correct
4 Correct 2210 ms 551496 KB Output is correct
5 Correct 2295 ms 461816 KB Output is correct
6 Correct 1967 ms 370692 KB Output is correct
7 Correct 2372 ms 338180 KB Output is correct
8 Correct 2339 ms 342984 KB Output is correct
9 Correct 2341 ms 327368 KB Output is correct
10 Correct 3777 ms 411484 KB Output is correct
11 Correct 2974 ms 457340 KB Output is correct
12 Correct 3504 ms 415316 KB Output is correct
13 Correct 2977 ms 581120 KB Output is correct
14 Correct 189 ms 145300 KB Output is correct
15 Correct 1593 ms 262204 KB Output is correct
16 Correct 2370 ms 346788 KB Output is correct
17 Correct 2375 ms 345704 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 111324 KB Output is correct
2 Correct 111 ms 110676 KB Output is correct
3 Correct 121 ms 110648 KB Output is correct
4 Correct 122 ms 111204 KB Output is correct
5 Correct 128 ms 110932 KB Output is correct
6 Correct 94 ms 110416 KB Output is correct
7 Correct 2541 ms 302028 KB Output is correct
8 Correct 2597 ms 322876 KB Output is correct
9 Correct 2561 ms 321488 KB Output is correct
10 Correct 3615 ms 430688 KB Output is correct
11 Correct 3646 ms 366200 KB Output is correct
12 Correct 3984 ms 392564 KB Output is correct
13 Correct 2537 ms 322108 KB Output is correct
14 Correct 1932 ms 340464 KB Output is correct
15 Correct 1963 ms 384572 KB Output is correct
16 Correct 2102 ms 420152 KB Output is correct
17 Correct 2210 ms 551496 KB Output is correct
18 Correct 2295 ms 461816 KB Output is correct
19 Correct 1967 ms 370692 KB Output is correct
20 Correct 2372 ms 338180 KB Output is correct
21 Correct 2339 ms 342984 KB Output is correct
22 Correct 2341 ms 327368 KB Output is correct
23 Correct 3777 ms 411484 KB Output is correct
24 Correct 2974 ms 457340 KB Output is correct
25 Correct 3504 ms 415316 KB Output is correct
26 Correct 2977 ms 581120 KB Output is correct
27 Correct 189 ms 145300 KB Output is correct
28 Correct 1593 ms 262204 KB Output is correct
29 Correct 2370 ms 346788 KB Output is correct
30 Correct 2375 ms 345704 KB Output is correct
31 Correct 2719 ms 394684 KB Output is correct
32 Correct 2529 ms 331388 KB Output is correct
33 Correct 2028 ms 304696 KB Output is correct
34 Correct 2534 ms 359288 KB Output is correct
35 Correct 2551 ms 345724 KB Output is correct
36 Correct 3924 ms 416416 KB Output is correct
37 Correct 3643 ms 615552 KB Output is correct
38 Correct 3794 ms 640828 KB Output is correct
39 Correct 3443 ms 539108 KB Output is correct
40 Correct 2503 ms 358404 KB Output is correct