oj.uz

Submission #388071

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

const int N = 1000001;

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 167 ms 96068 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 4532 ms 87080 KB Output is correct
2 Correct 4517 ms 107692 KB Output is correct
3 Correct 4267 ms 107876 KB Output is correct
4 Correct 1811 ms 106600 KB Output is correct
5 Correct 2136 ms 107312 KB Output is correct
6 Correct 3219 ms 89580 KB Output is correct
7 Correct 4439 ms 107836 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1066 ms 88596 KB Output is correct
2 Correct 898 ms 88504 KB Output is correct
3 Correct 803 ms 88040 KB Output is correct
4 Correct 799 ms 88492 KB Output is correct
5 Correct 1344 ms 88516 KB Output is correct
6 Correct 1241 ms 88644 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1066 ms 88596 KB Output is correct
2 Correct 898 ms 88504 KB Output is correct
3 Correct 803 ms 88040 KB Output is correct
4 Correct 799 ms 88492 KB Output is correct
5 Correct 1344 ms 88516 KB Output is correct
6 Correct 1241 ms 88644 KB Output is correct
7 Correct 2172 ms 88552 KB Output is correct
8 Correct 2141 ms 88704 KB Output is correct
9 Correct 1933 ms 88492 KB Output is correct
10 Correct 1078 ms 88052 KB Output is correct
11 Correct 1020 ms 88748 KB Output is correct
12 Correct 1583 ms 88744 KB Output is correct
13 Correct 1585 ms 88552 KB Output is correct
14 Correct 156 ms 8128 KB Output is correct
15 Correct 627 ms 43232 KB Output is correct
16 Correct 2286 ms 88520 KB Output is correct
17 Correct 2153 ms 73000 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 167 ms 96068 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -