oj.uz

Submission #388074

# Submission time Handle Problem Language Result Execution time Memory
388074 2021-04-09T21:48:52 Z timmyfeng Sweeping (JOI20_sweeping) C++17
100 / 100
 5088 ms 112768 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;
        assert ( k < N );
        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];
        prv[d][indices[pl]] = 0;
        tail[d][0] = indices[pr];
        nxt[d][indices[pr]] = 0;
    }

    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
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 844 KB Output is correct
2 Correct 7 ms 716 KB Output is correct
3 Correct 5 ms 716 KB Output is correct
4 Correct 6 ms 844 KB Output is correct
5 Correct 9 ms 796 KB Output is correct
6 Correct 2 ms 588 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4611 ms 87084 KB Output is correct
2 Correct 4510 ms 87148 KB Output is correct
3 Correct 4263 ms 87032 KB Output is correct
4 Correct 1837 ms 86660 KB Output is correct
5 Correct 2157 ms 86852 KB Output is correct
6 Correct 3245 ms 69136 KB Output is correct
7 Correct 4480 ms 87096 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1071 ms 88800 KB Output is correct
2 Correct 905 ms 88516 KB Output is correct
3 Correct 812 ms 88080 KB Output is correct
4 Correct 801 ms 88660 KB Output is correct
5 Correct 1376 ms 88568 KB Output is correct
6 Correct 1271 ms 88664 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1071 ms 88800 KB Output is correct
2 Correct 905 ms 88516 KB Output is correct
3 Correct 812 ms 88080 KB Output is correct
4 Correct 801 ms 88660 KB Output is correct
5 Correct 1376 ms 88568 KB Output is correct
6 Correct 1271 ms 88664 KB Output is correct
7 Correct 2237 ms 88664 KB Output is correct
8 Correct 2136 ms 88704 KB Output is correct
9 Correct 1999 ms 88936 KB Output is correct
10 Correct 1097 ms 88180 KB Output is correct
11 Correct 1055 ms 88560 KB Output is correct
12 Correct 1639 ms 88548 KB Output is correct
13 Correct 1649 ms 88612 KB Output is correct
14 Correct 173 ms 8132 KB Output is correct
15 Correct 621 ms 43204 KB Output is correct
16 Correct 2293 ms 88664 KB Output is correct
17 Correct 2189 ms 73024 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 844 KB Output is correct
2 Correct 7 ms 716 KB Output is correct
3 Correct 5 ms 716 KB Output is correct
4 Correct 6 ms 844 KB Output is correct
5 Correct 9 ms 796 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 4611 ms 87084 KB Output is correct
8 Correct 4510 ms 87148 KB Output is correct
9 Correct 4263 ms 87032 KB Output is correct
10 Correct 1837 ms 86660 KB Output is correct
11 Correct 2157 ms 86852 KB Output is correct
12 Correct 3245 ms 69136 KB Output is correct
13 Correct 4480 ms 87096 KB Output is correct
14 Correct 1071 ms 88800 KB Output is correct
15 Correct 905 ms 88516 KB Output is correct
16 Correct 812 ms 88080 KB Output is correct
17 Correct 801 ms 88660 KB Output is correct
18 Correct 1376 ms 88568 KB Output is correct
19 Correct 1271 ms 88664 KB Output is correct
20 Correct 2237 ms 88664 KB Output is correct
21 Correct 2136 ms 88704 KB Output is correct
22 Correct 1999 ms 88936 KB Output is correct
23 Correct 1097 ms 88180 KB Output is correct
24 Correct 1055 ms 88560 KB Output is correct
25 Correct 1639 ms 88548 KB Output is correct
26 Correct 1649 ms 88612 KB Output is correct
27 Correct 173 ms 8132 KB Output is correct
28 Correct 621 ms 43204 KB Output is correct
29 Correct 2293 ms 88664 KB Output is correct
30 Correct 2189 ms 73024 KB Output is correct
31 Correct 2690 ms 99640 KB Output is correct
32 Correct 4578 ms 107900 KB Output is correct
33 Correct 4462 ms 107872 KB Output is correct
34 Correct 5088 ms 112768 KB Output is correct
35 Correct 4974 ms 112620 KB Output is correct
36 Correct 2529 ms 106856 KB Output is correct
37 Correct 2608 ms 109888 KB Output is correct
38 Correct 3699 ms 107804 KB Output is correct
39 Correct 3961 ms 107560 KB Output is correct
40 Correct 4798 ms 107900 KB Output is correct