Submission #218043

#	Time	Username	Problem	Language	Result	Execution time	Memory
218043		Akashi	Sweeping (JOI20_sweeping)	C++14	100 / 100	10192 ms	175376 KiB

sweeping

#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 (stderr)

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 / 1
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 53 / 53
• Subtask 5: 25 / 25