oj.uz

Submission #743073

# Submission time Handle Problem Language Result Execution time Memory
743073 2023-05-17T07:45:31 Z piOOE Sweeping (JOI20_sweeping) C++17
100 / 100
 7172 ms 75840 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int inf = 1e9 + 7;

mt19937 rnd(228);

void ckmax(int &x, int y) {
    if (x < y) {
        x = y;
    }
}

struct Node {
    int prior = 0, sz = 0;
    int x = 0, y = 0, mxy = 0, mny = inf;
    int pushx = -1, pushy = -1;
    int L = 0, R = 0, par = 0;

    Node() = default;
    Node(int prior, int x, int y, int siz) : prior(prior), x(x), y(y), sz(siz), mxy(y), mny(y) {}
};

vector<Node> t{{}};

int create(Node b = Node()) {
    t.emplace_back(b);
    return t.size() - 1;
}

void apply(int p, int pushx, int pushy) {
    if (p == 0) {
        return;
    }
    ckmax(t[p].x, pushx);
    ckmax(t[p].pushx, pushx);
    ckmax(t[p].y, pushy);
    ckmax(t[p].pushy, pushy);
    ckmax(t[p].mxy, t[p].y);
    ckmax(t[p].mny, pushy);
}

void push(int x) {
    for (int p : {t[x].L, t[x].R}) {
        apply(p, t[x].pushx, t[x].pushy);
    }
    t[x].pushx = t[x].pushy = -1;
}

void pull(int x) {
    t[x].sz = 1 + t[t[x].L].sz + t[t[x].R].sz;
    t[x].mxy = max({t[x].y, t[t[x].L].mxy, t[t[x].R].mxy});
    t[x].mny = min({t[x].y, t[t[x].L].mny, t[t[x].R].mny});
    for (int p : {t[x].L, t[x].R}) {
        if (p) {
            t[p].par = x;
        }
    }
}

int merge(int l, int r) {
    t[l].par = t[r].par = 0;
    if (!l || !r) {
        return l ^ r;
    }
    push(l), push(r);
    if (t[l].prior > t[r].prior) {
        t[l].R = merge(t[l].R, r);
        pull(l);
        return l;
    } else {
        t[r].L = merge(l, t[r].L);
        pull(r);
        return r;
    }
}


//key <= k
pair<int, int> split_x(int x, int k) {
    if (!x) {
        return {};
    }
    t[x].par = 0;
    push(x);
    if (t[x].x > k) {
        auto se = split_x(t[x].L, k);
        t[x].L = se.second;
        pull(x);
        return {se.first, x};
    } else {
        auto se = split_x(t[x].R, k);
        t[x].R = se.first;
        pull(x);
        return {x, se.second};
    }
}

int super_merge(int x, int y) {
    t[x].par = t[y].par = 0;
    if (!x || !y) {
        return x ^ y;
    }
    push(x), push(y);
    if (t[x].prior < t[y].prior) {
        swap(x, y);
    }
    auto [l, r] = split_x(y, t[x].x);
    t[x].L = super_merge(t[x].L, l);
    t[x].R = super_merge(t[x].R, r);
    pull(x);
    return x;
}

//left.y <= k
pair<int, int> split_y(int x, int k) {
    t[x].par = 0;
    if (!x || t[x].mxy <= k) {
        return {x, 0};
    } else if (t[x].mny > k) {
        return {0, x};
    }
    push(x);
    auto [ly, lx] = split_y(t[x].L, k);
    auto [ry, rx] = split_y(t[x].R, k);
    if (t[x].y <= k) {
        t[x].L = ly, t[x].R = ry;
        pull(x);
        return {x, merge(lx, rx)};
    } else {
        t[x].L = lx, t[x].R = rx;
        pull(x);
        return {merge(ly, ry), x};
    }
}

pair<int, int> getValue(int x) {
    int px = t[x].x, py = t[x].y;
    while (x > 0) {
        ckmax(px, t[x].pushx);
        ckmax(py, t[x].pushy);
        x = t[x].par;
    }
    return {px, py};
}

void debug_node(int x, string pref = "") {
    if (!x) {
        return;
    }
    pref += "->" + to_string(x);
    debug_node(t[x].L, pref);
    cout << pref << endl;
    debug_node(t[x].R, pref);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    cin >> n >> m >> q;

    vector<int> pos(m + q);

    int root = 0;

    vector<int> X(m), Y(m), ord(m);
    for (int i = 0; i < m; ++i) {
        cin >> X[i] >> Y[i];
    }

    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) {
        return X[i] < X[j];
    });

    for (int i : ord) {
        int x = X[i], y = Y[i];
        pos[i] = create(Node(rnd(), x, y, 1));
        root = merge(root, pos[i]);
    }

    for (int qwq = 1; qwq <= q; ++qwq) {
        int T;
        cin >> T;

        if (T == 1) {
            int p;
            cin >> p;
            auto [x, y] = getValue(pos[p - 1]);
            cout << x << " " << y << '\n';
        } else if (T == 2) {
            int H;
            cin >> H;
            auto [l, r] = split_y(root, H);
            apply(l, n - H, 0);
            root = super_merge(l, r);
        } else if (T == 3) {
            int V;
            cin >> V;
            auto [l, r] = split_x(root, V);
            apply(l, 0, n - V);
            root = merge(l, r);
        } else {
            int x, y;
            cin >> x >> y;
            pos[m] = create(Node(rnd(), x, y, 1));
            auto [l, r] = split_x(root, x);
            root = merge(l, merge(pos[m], r));
            m += 1;
        }
    }

    return 0;
}

Compilation message

sweeping.cpp: In constructor 'Node::Node(int, int, int, int)':
sweeping.cpp:18:16: warning: 'Node::y' will be initialized after [-Wreorder]
   18 |     int x = 0, y = 0, mxy = 0, mny = inf;
      |                ^
sweeping.cpp:17:20: warning:   'int Node::sz' [-Wreorder]
   17 |     int prior = 0, sz = 0;
      |                    ^~
sweeping.cpp:23:5: warning:   when initialized here [-Wreorder]
   23 |     Node(int prior, int x, int y, int siz) : prior(prior), x(x), y(y), sz(siz), mxy(y), mny(y) {}
      |     ^~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 724 KB Output is correct
2 Correct 6 ms 424 KB Output is correct
3 Correct 6 ms 724 KB Output is correct
4 Correct 8 ms 724 KB Output is correct
5 Correct 13 ms 676 KB Output is correct
6 Correct 3 ms 596 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5508 ms 72244 KB Output is correct
2 Correct 7172 ms 72304 KB Output is correct
3 Correct 5993 ms 72276 KB Output is correct
4 Correct 5349 ms 71496 KB Output is correct
5 Correct 5661 ms 72004 KB Output is correct
6 Correct 6564 ms 68140 KB Output is correct
7 Correct 6318 ms 72256 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4726 ms 63364 KB Output is correct
2 Correct 3489 ms 63348 KB Output is correct
3 Correct 4319 ms 62164 KB Output is correct
4 Correct 2970 ms 63092 KB Output is correct
5 Correct 2773 ms 63160 KB Output is correct
6 Correct 4054 ms 62696 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 4726 ms 63364 KB Output is correct
2 Correct 3489 ms 63348 KB Output is correct
3 Correct 4319 ms 62164 KB Output is correct
4 Correct 2970 ms 63092 KB Output is correct
5 Correct 2773 ms 63160 KB Output is correct
6 Correct 4054 ms 62696 KB Output is correct
7 Correct 4777 ms 63040 KB Output is correct
8 Correct 4278 ms 63312 KB Output is correct
9 Correct 4453 ms 63336 KB Output is correct
10 Correct 5620 ms 62224 KB Output is correct
11 Correct 3513 ms 63136 KB Output is correct
12 Correct 4134 ms 63272 KB Output is correct
13 Correct 4161 ms 63160 KB Output is correct
14 Correct 130 ms 8064 KB Output is correct
15 Correct 1597 ms 59316 KB Output is correct
16 Correct 5549 ms 63252 KB Output is correct
17 Correct 4098 ms 63236 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 724 KB Output is correct
2 Correct 6 ms 424 KB Output is correct
3 Correct 6 ms 724 KB Output is correct
4 Correct 8 ms 724 KB Output is correct
5 Correct 13 ms 676 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 5508 ms 72244 KB Output is correct
8 Correct 7172 ms 72304 KB Output is correct
9 Correct 5993 ms 72276 KB Output is correct
10 Correct 5349 ms 71496 KB Output is correct
11 Correct 5661 ms 72004 KB Output is correct
12 Correct 6564 ms 68140 KB Output is correct
13 Correct 6318 ms 72256 KB Output is correct
14 Correct 4726 ms 63364 KB Output is correct
15 Correct 3489 ms 63348 KB Output is correct
16 Correct 4319 ms 62164 KB Output is correct
17 Correct 2970 ms 63092 KB Output is correct
18 Correct 2773 ms 63160 KB Output is correct
19 Correct 4054 ms 62696 KB Output is correct
20 Correct 4777 ms 63040 KB Output is correct
21 Correct 4278 ms 63312 KB Output is correct
22 Correct 4453 ms 63336 KB Output is correct
23 Correct 5620 ms 62224 KB Output is correct
24 Correct 3513 ms 63136 KB Output is correct
25 Correct 4134 ms 63272 KB Output is correct
26 Correct 4161 ms 63160 KB Output is correct
27 Correct 130 ms 8064 KB Output is correct
28 Correct 1597 ms 59316 KB Output is correct
29 Correct 5549 ms 63252 KB Output is correct
30 Correct 4098 ms 63236 KB Output is correct
31 Correct 3875 ms 72340 KB Output is correct
32 Correct 4461 ms 72212 KB Output is correct
33 Correct 4177 ms 72324 KB Output is correct
34 Correct 6561 ms 75840 KB Output is correct
35 Correct 5311 ms 75768 KB Output is correct
36 Correct 3948 ms 71468 KB Output is correct
37 Correct 4426 ms 71940 KB Output is correct
38 Correct 5072 ms 72216 KB Output is correct
39 Correct 4214 ms 72124 KB Output is correct
40 Correct 4125 ms 71928 KB Output is correct