Submission #387953

#	Time	Username	Problem	Language	Result	Execution time	Memory
387953		timmyfeng	Sweeping (JOI20_sweeping)	C++17	0 / 100	3254 ms	520308 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<array<int, 2>> 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}};
    int k = 1;

    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[k] = n - l, yl[k] = yl[j], yl[j] = l;
                triangles[n - l] = k;

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

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

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

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