Submission #894780

#	Time	Username	Problem	Language	Result	Execution time	Memory
894780		box	Sweeping (JOI20_sweeping)	C++17	100 / 100	3227 ms	355608 KiB

sweeping

#include <bits/stdc++.h>
using namespace std;

#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;
using pii = pair<int, int>;

const int MAXQ = 15e5;

int N, M, Q;
vector<pii> points;
bool alive[MAXQ];
vector<int> ask; vector<pii> ans;

list<int> under[MAXQ * 2];
int parent[MAXQ * 2];
int p[MAXQ * 2], sz[MAXQ * 2], mx[MAXQ * 2];
int tt;

void clear() {
    while (tt > 0)
        exchange(under[--tt], {});
}

int newnode(int x, int i) {
    int v = tt++;
    p[v] = v;
    mx[v] = x;
    sz[v] = 1;
    if (~i) under[v].push_back(i), parent[i] = v;
    return v;
}

int find(int i) {
    return p[i] == i ? i : p[i] = find(p[i]);
}

int merge(int i, int j) {
    i = find(i);
    j = find(j);
    if (i == j) return i;
    if (sz[i] < sz[j]) swap(i, j);
    p[j] = i;
    sz[i] += sz[j];
    mx[i] = max(mx[i], mx[j]);
    under[i].splice(end(under[i]), under[j]);
    return i;
}

pii qry_point(int i) {
    return {mx[find(parent[i * 2])], mx[find(parent[i * 2 + 1])]};
}


void rec(int X, int Y, vector<pii> qry) {
    if (sz(qry) == 0) return;
    if (X + Y == N) {
        for (auto [t, p] : qry) if (t == 1)
            ans[p] = points[ask[p]];
    } else {
        clear();
        int x_mid = X + (N - X - Y) / 2 + 1;
        int y_mid = N + 1 - x_mid;
        vector<pii> qry_one, qry_two;
        priority_queue<pii, vector<pii>, greater<pii>> qu_x, qu_y;
        for (auto [t, p] : qry) {
            if (t == 1) {
                int i = ask[p];
                if (points[i].first >= x_mid) qry_one.push_back({t, p});
                else if (points[i].second >= y_mid) qry_two.push_back({t, p});
                else ans[p] = qry_point(i);
            } else if (t == 2) {
                if (p >= y_mid) {
                    int v = newnode(N - p, -1);
                    while (sz(qu_x) && qu_x.top().first < N - p) {
                        v = merge(v, qu_x.top().second);
                        qu_x.pop();
                    }
                    qry_two.push_back({t, p});
                    qu_x.push({N - p, v});
                } else {
                    while (sz(qu_y) && qu_y.top().first <= p) {
                        for (int i : under[qu_y.top().second]) {
                            i /= 2;
                            if (alive[i]) {
                                points[i] = qry_point(i);
                                points[i].first = N - p;
                                alive[i] = false;
                                qry_one.push_back({4, i});
                            }
                        }
                        qu_y.pop();
                    }
                    qry_one.push_back({t, p});
                }
            } else if (t == 3) {
                if (p >= x_mid) {
                    int v = newnode(N - p, -1);
                    while (sz(qu_y) && qu_y.top().first < N - p) {
                        v = merge(v, qu_y.top().second);
                        qu_y.pop();
                    }
                    qry_one.push_back({t, p});
                    qu_y.push({N - p, v});
                } else {
                    while (sz(qu_x) && qu_x.top().first <= p) {
                        for (int i : under[qu_x.top().second]) {
                            i /= 2;
                            if (alive[i]) {
                                points[i] = qry_point(i);
                                points[i].second = N - p;
                                alive[i] = false;
                                qry_two.push_back({4, i});
                            }
                        }
                        qu_x.pop();
                    }
                    qry_two.push_back({t, p});
                }
            } else if (t == 4) {
                if (points[p].first >= x_mid) qry_one.push_back({t, p});
                else if (points[p].second >= y_mid) qry_two.push_back({t, p});
                else {
                    alive[p] = 1;
                    qu_x.push({points[p].first, newnode(points[p].first, p * 2)});
                    qu_y.push({points[p].second, newnode(points[p].second, p * 2 + 1)});
                }
            }
        }
        rec(x_mid, Y, qry_one);
        rec(X, y_mid, qry_two);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> M >> Q;
    vector<pii> qry;
    points.reserve(M + Q);
    ask.reserve(Q);
    ans.reserve(Q);
    for (int i = 0; i < M + Q; i++) {
        int t = 4;
        if (i >= M) cin >> t;
        if (t == 1) {
            int i; cin >> i, i--;
            qry.push_back({1, sz(ans)});
            ask.push_back(i);
            ans.push_back({-1, -1});
        } else if (t == 2) {
            int l; cin >> l;
            qry.push_back({2, l});
        } else if (t == 3) {
            int l; cin >> l;
            qry.push_back({3, l});
        } else {
            int x, y; cin >> x >> y;
            qry.push_back({4, sz(points)});
            points.push_back({x, y});
        }
    }
    rec(0, 0, qry);
    for (auto [x, y] : ans) cout << x << ' ' << y << '\n';
}

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 53 / 53
• Subtask 5: 25 / 25