oj.uz

Submission #388057

# Submission time Handle Problem Language Result Execution time Memory
388057 2021-04-09T20:03:18 Z timmyfeng Sweeping (JOI20_sweeping) C++17
64 / 100
 7150 ms 520264 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<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.0

# Verdict Execution time Memory Grader output
1 Runtime error 361 ms 382000 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 3073 ms 520264 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5232 ms 297824 KB Output is correct
2 Correct 4220 ms 297944 KB Output is correct
3 Correct 2611 ms 297356 KB Output is correct
4 Correct 2481 ms 296992 KB Output is correct
5 Correct 4532 ms 297528 KB Output is correct
6 Correct 4525 ms 297832 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 5232 ms 297824 KB Output is correct
2 Correct 4220 ms 297944 KB Output is correct
3 Correct 2611 ms 297356 KB Output is correct
4 Correct 2481 ms 296992 KB Output is correct
5 Correct 4532 ms 297528 KB Output is correct
6 Correct 4525 ms 297832 KB Output is correct
7 Correct 7150 ms 297876 KB Output is correct
8 Correct 6937 ms 297944 KB Output is correct
9 Correct 6790 ms 297848 KB Output is correct
10 Correct 4099 ms 297512 KB Output is correct
11 Correct 3615 ms 297940 KB Output is correct
12 Correct 5942 ms 297908 KB Output is correct
13 Correct 4949 ms 297924 KB Output is correct
14 Correct 290 ms 188800 KB Output is correct
15 Correct 2130 ms 266864 KB Output is correct
16 Correct 6975 ms 297864 KB Output is correct
17 Correct 6361 ms 294180 KB Output is correct

Subtask #5
0 / 25.0

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