oj.uz

Submission #894780

# Submission time Handle Problem Language Result Execution time Memory
894780 2023-12-29T01:29:36 Z box Sweeping (JOI20_sweeping) C++17
100 / 100
 3227 ms 355608 KB 
#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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 79188 KB Output is correct
2 Correct 23 ms 78940 KB Output is correct
3 Correct 18 ms 79196 KB Output is correct
4 Correct 23 ms 79236 KB Output is correct
5 Correct 22 ms 79196 KB Output is correct
6 Correct 18 ms 79196 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2017 ms 190708 KB Output is correct
2 Correct 1944 ms 190896 KB Output is correct
3 Correct 1983 ms 192688 KB Output is correct
4 Correct 1788 ms 239108 KB Output is correct
5 Correct 2812 ms 216128 KB Output is correct
6 Correct 2529 ms 223260 KB Output is correct
7 Correct 1965 ms 188820 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2064 ms 202668 KB Output is correct
2 Correct 2106 ms 208824 KB Output is correct
3 Correct 1570 ms 228880 KB Output is correct
4 Correct 2159 ms 316568 KB Output is correct
5 Correct 2168 ms 264068 KB Output is correct
6 Correct 1925 ms 208576 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2064 ms 202668 KB Output is correct
2 Correct 2106 ms 208824 KB Output is correct
3 Correct 1570 ms 228880 KB Output is correct
4 Correct 2159 ms 316568 KB Output is correct
5 Correct 2168 ms 264068 KB Output is correct
6 Correct 1925 ms 208576 KB Output is correct
7 Correct 2032 ms 201076 KB Output is correct
8 Correct 2039 ms 207608 KB Output is correct
9 Correct 2107 ms 198916 KB Output is correct
10 Correct 1983 ms 221212 KB Output is correct
11 Correct 2451 ms 279584 KB Output is correct
12 Correct 2880 ms 238052 KB Output is correct
13 Correct 2935 ms 329708 KB Output is correct
14 Correct 113 ms 111620 KB Output is correct
15 Correct 468 ms 173172 KB Output is correct
16 Correct 2043 ms 200008 KB Output is correct
17 Correct 1970 ms 205592 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 79188 KB Output is correct
2 Correct 23 ms 78940 KB Output is correct
3 Correct 18 ms 79196 KB Output is correct
4 Correct 23 ms 79236 KB Output is correct
5 Correct 22 ms 79196 KB Output is correct
6 Correct 18 ms 79196 KB Output is correct
7 Correct 2017 ms 190708 KB Output is correct
8 Correct 1944 ms 190896 KB Output is correct
9 Correct 1983 ms 192688 KB Output is correct
10 Correct 1788 ms 239108 KB Output is correct
11 Correct 2812 ms 216128 KB Output is correct
12 Correct 2529 ms 223260 KB Output is correct
13 Correct 1965 ms 188820 KB Output is correct
14 Correct 2064 ms 202668 KB Output is correct
15 Correct 2106 ms 208824 KB Output is correct
16 Correct 1570 ms 228880 KB Output is correct
17 Correct 2159 ms 316568 KB Output is correct
18 Correct 2168 ms 264068 KB Output is correct
19 Correct 1925 ms 208576 KB Output is correct
20 Correct 2032 ms 201076 KB Output is correct
21 Correct 2039 ms 207608 KB Output is correct
22 Correct 2107 ms 198916 KB Output is correct
23 Correct 1983 ms 221212 KB Output is correct
24 Correct 2451 ms 279584 KB Output is correct
25 Correct 2880 ms 238052 KB Output is correct
26 Correct 2935 ms 329708 KB Output is correct
27 Correct 113 ms 111620 KB Output is correct
28 Correct 468 ms 173172 KB Output is correct
29 Correct 2043 ms 200008 KB Output is correct
30 Correct 1970 ms 205592 KB Output is correct
31 Correct 1885 ms 221348 KB Output is correct
32 Correct 2019 ms 199440 KB Output is correct
33 Correct 1939 ms 190624 KB Output is correct
34 Correct 2160 ms 209156 KB Output is correct
35 Correct 2203 ms 204548 KB Output is correct
36 Correct 1860 ms 217836 KB Output is correct
37 Correct 3227 ms 351076 KB Output is correct
38 Correct 2965 ms 355608 KB Output is correct
39 Correct 2589 ms 315628 KB Output is correct
40 Correct 1949 ms 212444 KB Output is correct