oj.uz

Submission #388072

# Submission time Handle Problem Language Result Execution time Memory
388072 2021-04-09T21:43:08 Z timmyfeng Sweeping (JOI20_sweeping) C++17
74 / 100
 4528 ms 143540 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1500000;

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], ans[N];
int type[N], query[N], 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;
}

void update(int pl, int pr, int ql, int qr) {
    iota(indices + pl, indices + pr + 1, pl);
    fill(group + pl, group + pr + 1, 0);
    x_min[0] = y_min[0] = 0;

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

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

        head[d][0] = indices[pl];
        tail[d][0] = indices[pr];
    }

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

    for (int i = ql; i <= qr; ++i) {
        if (type[i] == 1) {
            int p = query[i];
            if (pl <= p && p <= pr) {
                int j = group[p];
                ans[i][0] = max(x_min[j], point[p][0]);
                ans[i][1] = max(y_min[j], point[p][1]);
            }
        } else if (type[i] == 2) {
            int l = query[i];
            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[i] == 3) {
            int l = query[i];
            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]]);
                }
            }
        }
    }

    for (int i = pl; i <= pr; ++i) {
        int j = group[i];
        point[i][0] = max(x_min[j], point[i][0]);
        point[i][1] = max(y_min[j], point[i][1]);
    }
}

void solve(int l, int r) {
    if (l == r) {
        return;
    }

    int m = (l + r) / 2;

    solve(l, m);

    int a = 0, b = 0;
    for (int i = l; i <= m; ++i) {
        if (type[i] == 4) {
            if (a == 0) {
                a = query[i];
            }
            b = query[i];
        }
    }

    if (a != 0) {
        update(a, b, m + 1, r);
    }

    solve(m + 1, r);
}

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

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

    for (int i = 1; i <= m; ++i) {
        for (auto &j : point[i]) {
            cin >> j;
        }
    }

    int c = m;

    for (int i = 1; i <= q; ++i) {
        cin >> type[i];
        if (type[i] == 4) {
            query[i] = ++c;
            for (auto &j : point[c]) {
                cin >> j;
            }
        } else {
            cin >> query[i];
        }
    }

    update(1, m, 1, q);
    solve(1, q);

    for (int i = 1; i <= q; ++i) {
        if (type[i] == 1) {
            cout << ans[i][0] << " " << ans[i][1] << "\n";
        }
    }
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 844 KB Output is correct
2 Runtime error 268 ms 143540 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4528 ms 87100 KB Output is correct
2 Correct 4527 ms 87120 KB Output is correct
3 Correct 4309 ms 87140 KB Output is correct
4 Correct 1824 ms 86860 KB Output is correct
5 Correct 2132 ms 87076 KB Output is correct
6 Correct 3201 ms 69012 KB Output is correct
7 Correct 4495 ms 87112 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1067 ms 88708 KB Output is correct
2 Correct 939 ms 88612 KB Output is correct
3 Correct 809 ms 88032 KB Output is correct
4 Correct 808 ms 88668 KB Output is correct
5 Correct 1351 ms 88512 KB Output is correct
6 Correct 1276 ms 88552 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1067 ms 88708 KB Output is correct
2 Correct 939 ms 88612 KB Output is correct
3 Correct 809 ms 88032 KB Output is correct
4 Correct 808 ms 88668 KB Output is correct
5 Correct 1351 ms 88512 KB Output is correct
6 Correct 1276 ms 88552 KB Output is correct
7 Correct 2163 ms 88744 KB Output is correct
8 Correct 2114 ms 88780 KB Output is correct
9 Correct 1944 ms 88708 KB Output is correct
10 Correct 1088 ms 88304 KB Output is correct
11 Correct 1022 ms 88644 KB Output is correct
12 Correct 1630 ms 88536 KB Output is correct
13 Correct 1664 ms 88660 KB Output is correct
14 Correct 155 ms 8132 KB Output is correct
15 Correct 618 ms 43272 KB Output is correct
16 Correct 2313 ms 88744 KB Output is correct
17 Correct 2208 ms 72920 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 844 KB Output is correct
2 Runtime error 268 ms 143540 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -