Submission #388071

#	Time	Username	Problem	Language	Result	Execution time	Memory
388071		timmyfeng	Sweeping (JOI20_sweeping)	C++17	74 / 100	4532 ms	107876 KiB

sweeping

#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
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 53 / 53
• Subtask 5: 0 / 25