Submission #388057

#	Time	Username	Problem	Language	Result	Execution time	Memory
388057		timmyfeng	Sweeping (JOI20_sweeping)	C++17	64 / 100	7150 ms	520264 KiB

sweeping

#include <bits/stdc++.h>
using namespace std;

const int N = 1000001;

#include <bits/extc++.h>

template <class T, class Comp = less<T>>
using ordered_set = __gnu_pbds::tree<
    T, __gnu_pbds::null_type, Comp,
    __gnu_pbds::rb_tree_tag,
    __gnu_pbds::tree_order_statistics_node_update
>;

ordered_set<pair<int, int>> xs[N], ys[N];
int x[N], y[N], xl[N], yl[N], group[N];

void add(int i, int j) {
    int k = group[i];
    xs[k].erase({x[i], i});
    ys[k].erase({y[i], i});
    xs[j].insert({x[i], i});
    ys[j].insert({y[i], i});
    group[i] = j;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    cin >> n >> m >> q;

    for (int i = 1; i <= m; ++i) {
        cin >> x[i] >> y[i];
        xs[0].insert({x[i], i});
        ys[0].insert({y[i], i});
    }

    map<int, int> triangles = {{0, 0}};

    for (int i = 1; i <= q; ++i) {
        int type;
        cin >> type;

        if (type == 1) {
            int p;
            cin >> p;

            int j = group[p];
            cout << max(xl[j], x[p]) << " " << max(yl[j], y[p]) << "\n";
        } else if (type == 2) {
            int l;
            cin >> l;

            if (triangles.count(n - l) == 0) {
                int j = (--triangles.upper_bound(n - l))->second;
                xl[i] = n - l, yl[i] = yl[j], yl[j] = l + 1;
                triangles[n - l] = i;

                if (ys[j].order_of_key({l + 1, 0}) <= ys[j].size() / 2) {
                    while (!ys[j].empty() && ys[j].begin()->first <= l) {
                        add(ys[j].begin()->second, i);
                    }
                } else {
                    while (!ys[j].empty() && (--ys[j].end())->first > l) {
                        add((--ys[j].end())->second, i);
                    }
                    swap(xl[j], xl[i]), swap(yl[j], yl[i]);
                    swap(triangles[xl[j]], triangles[xl[i]]);
                }
            }
        } else if (type == 3) {
            int l;
            cin >> l;

            if (triangles.count(l + 1) == 0) {
                int j = (--triangles.upper_bound(l + 1))->second;
                yl[i] = yl[j], xl[i] = l + 1, yl[j] = n - l;
                triangles[l + 1] = i;

                if (xs[j].order_of_key({l + 1, 0}) <= xs[j].size() / 2) {
                    while (!xs[j].empty() && xs[j].begin()->first <= l) {
                        add(xs[j].begin()->second, i);
                    }
                    swap(xl[j], xl[i]), swap(yl[j], yl[i]);
                    swap(triangles[xl[j]], triangles[xl[i]]);
                } else {
                    while (!xs[j].empty() && (--xs[j].end())->first > l) {
                        add((--xs[j].end())->second, i);
                    }
                }
            }
        } else if (type == 4) {
            int a, b;
            cin >> a >> b;
            assert(false);
        }
    }
}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 10
• Subtask 3: 11 / 11
• Subtask 4: 53 / 53
• Subtask 5: 0 / 25