oj.uz

Submission #388052

# Submission time Handle Problem Language Result Execution time Memory
388052 2021-04-09T19:56:25 Z timmyfeng Sweeping (JOI20_sweeping) C++17
0 / 100
 5657 ms 520260 KB 
#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}};

    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()->at(0) <= l) {
                        add(ys[j].begin()->at(1), i);
                    }
                } else {
                    while (!ys[j].empty() && (--ys[j].end())->at(0) > l) {
                        add((--ys[j].end())->at(1), 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) == 0) {
                int j = (--triangles.upper_bound(l))->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()->at(0) <= l) {
                        add(xs[j].begin()->at(1), 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())->at(0) > l) {
                        add((--xs[j].end())->at(1), i);
                    }
                }
            }
        } else if (type == 4) {
            int a, b;
            cin >> a >> b;
            assert(false);
        }
    }
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Runtime error 443 ms 381944 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 3379 ms 520260 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5657 ms 297788 KB Output is correct
2 Correct 4360 ms 297804 KB Output is correct
3 Incorrect 2072 ms 295352 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 5657 ms 297788 KB Output is correct
2 Correct 4360 ms 297804 KB Output is correct
3 Incorrect 2072 ms 295352 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 443 ms 381944 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -