oj.uz

Submission #388070

# Submission time Handle Problem Language Result Execution time Memory
388070 2021-04-09T21:16:47 Z timmyfeng Sweeping (JOI20_sweeping) C++17
64 / 100
 2505 ms 73052 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
>;

int head[2][N], tail[2][N], prv[2][N], nxt[2][N];
int x_min[N], y_min[N], group[N], indices[N];
array<int, 2> point[N];

bool split(int i, int j, int l, int d) {
    bool flip = false;

    if (head[d][j] == 0) {
        head[d][i] = tail[d][i] = 0;
    } else {
        int h = head[d][j], t = tail[d][j];
        while (point[h][d] <= l && point[t][d] > l) {
            h = nxt[d][h], t = prv[d][t];
        }

        if (point[h][d] > l) {
            head[d][i] = h == head[d][j] ? 0 : head[d][j];
            tail[d][i] = prv[d][h];
            head[d][j] = h;

            nxt[d][prv[d][h]] = 0;
            prv[d][h] = 0;
        } else {
            flip = true;

            tail[d][i] = t == tail[d][j] ? 0 : tail[d][j];
            head[d][i] = nxt[d][t];
            tail[d][j] = t;

            prv[d][nxt[d][t]] = 0;
            nxt[d][t] = 0;
        }
    }

    d = 1 - d;

    int k = 0;
    for (int u = head[1 - d][i]; u != 0; u = nxt[1 - d][u]) {
        indices[k++] = u;
        group[u] = i;

        if (prv[d][u] == 0) {
            head[d][j] = nxt[d][u];
        }

        if (nxt[d][u] == 0) {
            tail[d][j] = prv[d][u];
        }

        nxt[d][prv[d][u]] = nxt[d][u];
        prv[d][nxt[d][u]] = prv[d][u];
    }

    if (k == 0) {
        head[d][i] = tail[d][i] = 0;
    } else {
        sort(indices, indices + k, [&](int u, int v) {
            return point[u][d] < point[v][d];
        });

        prv[d][indices[0]] = 0;
        head[d][i] = indices[0];
        nxt[d][indices[k - 1]] = 0;
        tail[d][i] = indices[k - 1];

        for (int i = 1; i < k; ++i) {
            nxt[d][indices[i - 1]] = indices[i];
            prv[d][indices[i]] = indices[i - 1];
        }
    }

    return flip;
}

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) {
        for (auto &j : point[i]) {
            cin >> j;
        }
    }

    iota(indices, indices + m, 1);
    for (int d = 0; d < 2; ++d) {
        sort(indices, indices + m, [&](int u, int v) {
            return point[u][d] < point[v][d];
        });

        for (int i = 1; i < m; ++i) {
            nxt[d][indices[i - 1]] = indices[i];
            prv[d][indices[i]] = indices[i - 1];
        }

        head[d][0] = indices[0];
        tail[d][0] = indices[m - 1];
    }

    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(x_min[j], point[p][0]) << " " << max(y_min[j], point[p][1]) << "\n";
        } else if (type == 2) {
            int l;
            cin >> l;

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

                if (split(i, j, l, 1)) {
                    swap(x_min[j], x_min[i]), swap(y_min[j], y_min[i]);
                    swap(triangles[x_min[j]], triangles[x_min[i]]);
                }
            }
        } else if (type == 3) {
            int l;
            cin >> l;

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

                if (!split(i, j, l, 0)) {
                    swap(x_min[j], x_min[i]), swap(y_min[j], y_min[i]);
                    swap(triangles[x_min[j]], triangles[x_min[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 4 ms 644 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 438 ms 32332 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 1159 ms 72784 KB Output is correct
2 Correct 986 ms 72740 KB Output is correct
3 Correct 858 ms 72520 KB Output is correct
4 Correct 838 ms 72048 KB Output is correct
5 Correct 1494 ms 72492 KB Output is correct
6 Correct 1387 ms 72720 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1159 ms 72784 KB Output is correct
2 Correct 986 ms 72740 KB Output is correct
3 Correct 858 ms 72520 KB Output is correct
4 Correct 838 ms 72048 KB Output is correct
5 Correct 1494 ms 72492 KB Output is correct
6 Correct 1387 ms 72720 KB Output is correct
7 Correct 2394 ms 73052 KB Output is correct
8 Correct 2312 ms 72956 KB Output is correct
9 Correct 2187 ms 72896 KB Output is correct
10 Correct 1185 ms 72532 KB Output is correct
11 Correct 1087 ms 72836 KB Output is correct
12 Correct 1813 ms 72768 KB Output is correct
13 Correct 1811 ms 72940 KB Output is correct
14 Correct 139 ms 452 KB Output is correct
15 Correct 619 ms 25616 KB Output is correct
16 Correct 2505 ms 72908 KB Output is correct
17 Correct 2284 ms 61272 KB Output is correct

Subtask #5
0 / 25.0

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