oj.uz

Submission #218043

# Submission time Handle Problem Language Result Execution time Memory
218043 2020-03-31T17:27:03 Z Akashi Sweeping (JOI20_sweeping) C++14
100 / 100
 10192 ms 175376 KB 
#include <bits/stdc++.h>
using namespace std;

struct query{
    int tip, x, y;
};
query a[1500005];

int where[1500005];
struct min_max{
    vector <int> label;
    vector <vector <int> > arb;
    int parent[1500005];

    void init(){
        label.clear();
        arb.clear();
    }

    void create(int x, int ind){
        label.push_back(x);
        arb.emplace_back();

        if(ind != -1){
            arb.back().push_back(ind);
            parent[ind] = label.size() - 1;
        }
    }

    void push(int x, int ind){
        arb[x].push_back(ind);
        parent[ind] = x;
    }

    int merge(int x, int y){
        if(arb[x].size() < arb[y].size()) swap(x, y);

        for(auto ind : arb[y]){
            if(where[ind]) continue ;
            push(x, ind);
        }

        label[x] = max(label[x], label[y]);
        return x;
    }

    int find(int ind){
        return label[parent[ind]];
    }
};
min_max xCords, yCords;

int n, m, q;
pair <int, int> ans[1500005];
priority_queue <pair <int, int>, vector <pair <int, int> > , greater <pair <int, int> > > pqX, pqY;

int NR = 0;
void solve(int x, int y, vector <int> op){
    if(!op.size()) return ;
    int dif = n - x - y;
    if(dif == 0){
        for(auto i : op)
            if(a[i].tip == 1)
            ans[i] = {x, y};
        return ;
    }

    int X = x + (dif + 1) / 2, Y = y + dif / 2 + 1;
    vector <int> opX, opY;

    sort(op.begin(), op.end());

    xCords.init(); yCords.init();

    for(auto i : op){
        if(a[i].tip == 1){
            if(where[a[i].x]){
                if(where[a[i].x] == 1) opX.push_back(i);
                else opY.push_back(i);
            }
            else ans[i] = {xCords.find(a[i].x), yCords.find(a[i].x)};
        }
        else if(a[i].tip == 4){
            if(a[i].x >= X){
                where[i] = 1;
                opX.push_back(i);
            }
            else if(a[i].y >= Y){
                where[i] = 2;
                opY.push_back(i);
            }
            else{
                where[i] = 0;
                xCords.create(a[i].x, i);
                yCords.create(a[i].y, i);
                pqX.push({a[i].x, xCords.parent[i]});
                pqY.push({a[i].y, yCords.parent[i]});
            }
        }
        else if(a[i].tip == 2){
            if(n - a[i].x < X){
                opY.push_back(i);

                xCords.create(n - a[i].x, -1);
                int ind = xCords.label.size() - 1;
                while(!pqX.empty() && pqX.top().first <= n - a[i].x){
                    int ind2 = pqX.top().second;
                    pqX.pop();

                    ind = xCords.merge(ind, ind2);
                }
                pqX.push({n - a[i].x, ind});
            }
            else{
                opX.push_back(i);

                while(!pqY.empty() && pqY.top().first <= a[i].x){
                    int ind = pqY.top().second;
                    pqY.pop();

                    for(auto it : yCords.arb[ind]){
                        if(where[it]) continue ;
                        where[it] = 1;
                        opX.push_back(it);
                    }
                }
            }
        }
        else if(a[i].tip == 3){
            if(n - a[i].x < Y){
                opX.push_back(i);

                yCords.create(n - a[i].x, -1);
                int ind = yCords.label.size() - 1;
                while(!pqY.empty() && pqY.top().first <= n - a[i].x){
                    int ind2 = pqY.top().second;
                    pqY.pop();

                    ind = yCords.merge(ind, ind2);
                }
                pqY.push({n - a[i].x, ind});
            }
            else{
                opY.push_back(i);

                while(!pqX.empty() && pqX.top().first <= a[i].x){
                    int ind = pqX.top().second;
                    pqX.pop();

                    for(auto it : xCords.arb[ind]){
                        if(where[it]) continue ;
                        where[it] = 2;
                        opY.push_back(it);
                    }
                }
            }
        }
    }

    while(!pqX.empty()) pqX.pop();
    while(!pqY.empty()) pqY.pop();

    solve(X, y, opX);
    solve(x, Y, opY);
}

int get_ind[1500005];

int main()
{
    scanf("%d%d%d", &n, &m, &q);

    for(int i = 1; i <= m ; ++i){
        a[i].tip = 4;
        scanf("%d%d", &a[i].x, &a[i].y);
        get_ind[i] = i;
    }

    int NR = m;
    for(int i = m + 1; i <= q + m ; ++i){
        scanf("%d", &a[i].tip);
        scanf("%d", &a[i].x);
        if(a[i].tip == 1) a[i].x = get_ind[a[i].x];
        if(a[i].tip == 4){
            scanf("%d", &a[i].y);
            get_ind[++NR] = i;
        }
    }

    vector <int> op;
    for(int i = 1; i <= m + q ; ++i) op.push_back(i);

    solve(0, 0, op);

    for(int i = 1; i <= q + m ; ++i)
        if(a[i].tip == 1) printf("%d %d\n", ans[i].first, ans[i].second);

    return 0;
}

Compilation message

sweeping.cpp: In function 'int main()':
sweeping.cpp:171:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &m, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:175:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a[i].x, &a[i].y);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:181:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i].tip);
         ~~~~~^~~~~~~~~~~~~~~~~
sweeping.cpp:182:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i].x);
         ~~~~~^~~~~~~~~~~~~~~
sweeping.cpp:185:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &a[i].y);
             ~~~~~^~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 896 KB Output is correct
2 Correct 17 ms 896 KB Output is correct
3 Correct 10 ms 1152 KB Output is correct
4 Correct 18 ms 1024 KB Output is correct
5 Correct 19 ms 1024 KB Output is correct
6 Correct 8 ms 896 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3975 ms 86916 KB Output is correct
2 Correct 3978 ms 87976 KB Output is correct
3 Correct 3995 ms 87632 KB Output is correct
4 Correct 5631 ms 123140 KB Output is correct
5 Correct 5304 ms 121340 KB Output is correct
6 Correct 5536 ms 108652 KB Output is correct
7 Correct 3983 ms 88520 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4436 ms 84192 KB Output is correct
2 Correct 4745 ms 94596 KB Output is correct
3 Correct 4403 ms 116168 KB Output is correct
4 Correct 4410 ms 152212 KB Output is correct
5 Correct 5135 ms 132600 KB Output is correct
6 Correct 4933 ms 95056 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 4436 ms 84192 KB Output is correct
2 Correct 4745 ms 94596 KB Output is correct
3 Correct 4403 ms 116168 KB Output is correct
4 Correct 4410 ms 152212 KB Output is correct
5 Correct 5135 ms 132600 KB Output is correct
6 Correct 4933 ms 95056 KB Output is correct
7 Correct 4615 ms 91648 KB Output is correct
8 Correct 4801 ms 93116 KB Output is correct
9 Correct 4449 ms 89348 KB Output is correct
10 Correct 5975 ms 116932 KB Output is correct
11 Correct 6972 ms 141724 KB Output is correct
12 Correct 8005 ms 116776 KB Output is correct
13 Correct 8682 ms 158696 KB Output is correct
14 Correct 242 ms 30428 KB Output is correct
15 Correct 1055 ms 95740 KB Output is correct
16 Correct 4635 ms 97464 KB Output is correct
17 Correct 4766 ms 95912 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 896 KB Output is correct
2 Correct 17 ms 896 KB Output is correct
3 Correct 10 ms 1152 KB Output is correct
4 Correct 18 ms 1024 KB Output is correct
5 Correct 19 ms 1024 KB Output is correct
6 Correct 8 ms 896 KB Output is correct
7 Correct 3975 ms 86916 KB Output is correct
8 Correct 3978 ms 87976 KB Output is correct
9 Correct 3995 ms 87632 KB Output is correct
10 Correct 5631 ms 123140 KB Output is correct
11 Correct 5304 ms 121340 KB Output is correct
12 Correct 5536 ms 108652 KB Output is correct
13 Correct 3983 ms 88520 KB Output is correct
14 Correct 4436 ms 84192 KB Output is correct
15 Correct 4745 ms 94596 KB Output is correct
16 Correct 4403 ms 116168 KB Output is correct
17 Correct 4410 ms 152212 KB Output is correct
18 Correct 5135 ms 132600 KB Output is correct
19 Correct 4933 ms 95056 KB Output is correct
20 Correct 4615 ms 91648 KB Output is correct
21 Correct 4801 ms 93116 KB Output is correct
22 Correct 4449 ms 89348 KB Output is correct
23 Correct 5975 ms 116932 KB Output is correct
24 Correct 6972 ms 141724 KB Output is correct
25 Correct 8005 ms 116776 KB Output is correct
26 Correct 8682 ms 158696 KB Output is correct
27 Correct 242 ms 30428 KB Output is correct
28 Correct 1055 ms 95740 KB Output is correct
29 Correct 4635 ms 97464 KB Output is correct
30 Correct 4766 ms 95912 KB Output is correct
31 Correct 5321 ms 105808 KB Output is correct
32 Correct 4396 ms 93056 KB Output is correct
33 Correct 3835 ms 84552 KB Output is correct
34 Correct 5252 ms 114128 KB Output is correct
35 Correct 5104 ms 108116 KB Output is correct
36 Correct 6455 ms 131588 KB Output is correct
37 Correct 9583 ms 168756 KB Output is correct
38 Correct 10192 ms 175376 KB Output is correct
39 Correct 9258 ms 163868 KB Output is correct
40 Correct 4789 ms 99964 KB Output is correct