oj.uz

Submission #1057140

# Submission time Handle Problem Language Result Execution time Memory
1057140 2024-08-13T14:30:15 Z arbuzick Comparing Plants (IOI20_plants) C++17
100 / 100
 884 ms 220808 KB 
#include "plants.h"

#include <bits/stdc++.h>

using namespace std;

int n, k;

constexpr int R = 1 << 18;

int blocked[R * 2];

pair<int, int> mn[R * 2];

pair<int, int> mn_free[R * 2];

int add[R * 2];

void build() {
    for (int i = 0; i < R; ++i) {
        mn[i + R] = mn_free[i + R] = make_pair(0, i);
    }
    for (int i = R - 1; i > 0; --i) {
        mn[i] = mn_free[i] = min(mn[i * 2], mn[i * 2 + 1]);
    }
}

void push(int node) {
    if (add[node] != 0) {
        mn[node * 2].first += add[node];
        mn_free[node * 2].first += add[node];
        add[node * 2] += add[node];
        mn[node * 2 + 1].first += add[node];
        mn_free[node * 2 + 1].first += add[node];
        add[node * 2 + 1] += add[node];
    }
    add[node] = 0;
}

void add_blocked(int ql, int qr, int val, int node = 1, int nl = 0, int nr = R) {
    if (ql <= nl && nr <= qr) {
        blocked[node] += val;
        if (blocked[node] == 0) {
            if (nl == nr - 1) {
                mn_free[node] = mn[node];
            } else {
                push(node);
                mn[node] = min(mn[node * 2], mn[node * 2 + 1]);
                mn_free[node] = min(mn_free[node * 2], mn_free[node * 2 + 1]);
            }
        } else {
            mn_free[node] = make_pair(R, -1);
        }
        return;
    }
    if (qr <= nl || nr <= ql) {
        return;
    }
    push(node);
    int nm = (nl + nr) / 2;
    add_blocked(ql, qr, val, node * 2, nl, nm);
    add_blocked(ql, qr, val, node * 2 + 1, nm, nr);
    mn[node] = min(mn[node * 2], mn[node * 2 + 1]);
    if (blocked[node] == 0) {
        mn_free[node] = min(mn_free[node * 2], mn_free[node * 2 + 1]);
    }
}

void add_val(int ql, int qr, int val, int node = 1, int nl = 0, int nr = R) {
    if (ql <= nl && nr <= qr) {
        mn[node].first += val;
        mn_free[node].first += val;
        add[node] += val;
        return;
    }
    if (qr <= nl || nr <= ql) {
        return;
    }
    push(node);
    int nm = (nl + nr) / 2;
    add_val(ql, qr, val, node * 2, nl, nm);
    add_val(ql, qr, val, node * 2 + 1, nm, nr);
    mn[node] = min(mn[node * 2], mn[node * 2 + 1]);
    if (blocked[node] == 0) {
        mn_free[node] = min(mn_free[node * 2], mn_free[node * 2 + 1]);
    }
}

int get_free_zero(int node = 1, int nl = 0, int nr = R) {
    if (blocked[node]) {
        return -1;
    }
    // cout << nl << ' ' << nr << ' ' << mn[node].first << endl;
    if (mn_free[node].first != 0) {
        return -1;
    }
    if (nl == nr - 1) {
        return mn[node].second;
    }
    push(node);
    int nm = (nl + nr) / 2;
    int ans = get_free_zero(node * 2, nl, nm);
    if (ans == -1) {
        ans = get_free_zero(node * 2 + 1, nm, nr);
    }
    mn[node] = min(mn[node * 2], mn[node * 2 + 1]);
    mn_free[node] = min(mn_free[node * 2], mn_free[node * 2 + 1]);
    return ans;
}

void get_all_zero(int ql, int qr, vector<int> &ans, int node = 1, int nl = 0, int nr = R) {
    if (mn[node].first != 0) {
        return;
    }
    if (qr <= nl || nr <= ql) {
        return;
    }
    if (nl == nr - 1) {
        ans.push_back(mn[node].second);
        return;
    }
    push(node);
    int nm = (nl + nr) / 2;
    get_all_zero(ql, qr, ans, node * 2, nl, nm);
    get_all_zero(ql, qr, ans, node * 2 + 1, nm, nr);
    mn[node] = min(mn[node * 2], mn[node * 2 + 1]);
    if (blocked[node] == 0) {
        mn_free[node] = min(mn_free[node * 2], mn_free[node * 2 + 1]);
    }
}

constexpr int R2 = 1 << 20;

int mx[R2 * 2];

void build_mx() {
    for (int i = 1; i < R2 * 2; ++i) {
        mx[i] = -1;
    }
}

void _change(int pos, int val) {
    for (pos += R2; pos > 0; pos /= 2) {
        mx[pos] = max(mx[pos], val);
    }
}

void change(int pos, int val) {
    _change(pos, val);
    _change(pos + n, val);
    _change(pos + n * 2, val);
}

int _get(int l, int r) {
    l = max(0, l);
    r = min(R2, r);
    l += R2;
    r += R2;
    int ans = -1;
    while (l < r) {
        if (l & 1) {
            ans = max(ans, mx[l++]);
        }
        if (r & 1) {
            ans = max(ans, mx[--r]);
        }
        l >>= 1;
        r >>= 1;
    }
    return ans;
}

int get(int l, int r) {
    return _get(l + n, r + n);
}

constexpr int maxn = 2e5 + 5, lg = 20;

vector<int> ord;

int pos[maxn];

pair<pair<int, int>, int> go_left[lg][maxn][2], go_right[lg][maxn][2];

int prv_left[maxn][2], prv_right[maxn][2];

void init(int _k, vector<int> r) {
    n = r.size();
    k = _k;
    build();
    add_blocked(n, R, 1);
    for (int i = 0; i < n; ++i) {
        if (r[i] == 0) {
            if (i + k <= n) {
                add_blocked(i + 1, i + k, 1);
            } else {
                add_blocked(i + 1, n, 1);
                add_blocked(0, (i + k) % n, 1);
            }
        }
        add_val(i, i + 1, r[i]);
    }
    for (int _ = 0; _ < n; ++_) {
        int pos_mx = get_free_zero();
        // cout << pos_mx << endl;
        ord.push_back(pos_mx);
        vector<int> new_zero;
        if (pos_mx >= k - 1) {
            add_val(pos_mx - k + 1, pos_mx, -1);
            get_all_zero(pos_mx - k + 1, pos_mx, new_zero);
        } else {
            if (pos_mx > 0) {
                add_val(0, pos_mx, -1);
                get_all_zero(0, pos_mx, new_zero);
            }
            add_val(n - (k - pos_mx) + 1, n, -1);
            get_all_zero(n - (k - pos_mx) + 1, n, new_zero);
        }
        if (pos_mx + k <= n) {
            add_blocked(pos_mx + 1, pos_mx + k, -1);
        } else {
            add_blocked(pos_mx + 1, n, -1);
            add_blocked(0, (pos_mx + k) % n, -1);
        }
        add_val(pos_mx, pos_mx + 1, R);
        // cout << pos_mx << ' ' << new_zero.size() << endl;
        for (auto pos : new_zero) {
            if (pos + k <= n) {
                add_blocked(pos + 1, pos + k, 1);
            } else {
                add_blocked(pos + 1, n, 1);
                add_blocked(0, (pos + k) % n, 1);
            }
        }
    }
    reverse(ord.begin(), ord.end());
    build_mx();
    for (int i = 0; i < n; ++i) {
        prv_left[i][0] = get(ord[i] - k + 1, ord[i]);
        prv_left[i][1] = get(ord[i] - k + 1 - n, ord[i] - n);
        prv_right[i][0] = get(ord[i] + 1, ord[i] + k);
        prv_right[i][1] = get(ord[i] + 1 + n, ord[i] + k + n);
        change(ord[i], i);
        if (prv_left[i][0] != -1) {
            if (ord[i] - k < ord[prv_left[i][0]] && ord[prv_left[i][0]] < ord[i]) {
                go_left[0][i][0] = make_pair(make_pair(prv_left[i][0], 0), ord[prv_left[i][0]] - k);
            } else {
                go_left[0][i][0] = make_pair(make_pair(prv_left[i][0], 1), ord[prv_left[i][0]] - k - n);
            }
        } else {
            go_left[0][i][0] = make_pair(make_pair(-1, -1), R);
        }
        if (prv_left[i][1] != -1) {
            go_left[0][i][1] = make_pair(make_pair(prv_left[i][1], 1), ord[prv_left[i][1]] - k - n);
        } else {
            go_left[0][i][1] = make_pair(make_pair(-1, -1), R);
        }

        if (prv_right[i][0] != -1) {
            if (ord[i] < ord[prv_right[i][0]] && ord[prv_right[i][0]] < ord[i] + k) {
                go_right[0][i][0] = make_pair(make_pair(prv_right[i][0], 0), ord[prv_right[i][0]] + k);
            } else {
                go_right[0][i][0] = make_pair(make_pair(prv_right[i][0], 1), ord[prv_right[i][0]] + k + n);
            }
        } else {
            go_right[0][i][0] = make_pair(make_pair(-1, -1), -R);
        }
        if (prv_right[i][1] != -1) {
            go_right[0][i][1] = make_pair(make_pair(prv_right[i][1], 1), ord[prv_right[i][1]] + k + n);
        } else {
            go_right[0][i][1] = make_pair(make_pair(-1, -1), -R);
        }
    }
    for (int i = 1; i < lg; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k < 2; ++k) {
                if (go_left[i - 1][j][k].first.first != -1 && go_left[i - 1][go_left[i - 1][j][k].first.first][go_left[i - 1][j][k].first.second].first.first != -1) {
                    go_left[i][j][k].first.first = go_left[i - 1][go_left[i - 1][j][k].first.first][go_left[i - 1][j][k].first.second].first.first;
                    go_left[i][j][k].first.second = go_left[i - 1][go_left[i - 1][j][k].first.first][go_left[i - 1][j][k].first.second].first.second;
                    go_left[i][j][k].second = min(go_left[i - 1][j][k].second, go_left[i - 1][go_left[i - 1][j][k].first.first][go_left[i - 1][j][k].first.second].second);
                } else {
                    go_left[i][j][k] = make_pair(make_pair(-1, -1), R);
                }

                if (go_right[i - 1][j][k].first.first != -1 && go_right[i - 1][go_right[i - 1][j][k].first.first][go_right[i - 1][j][k].first.second].first.first != -1) {
                    go_right[i][j][k].first.first = go_right[i - 1][go_right[i - 1][j][k].first.first][go_right[i - 1][j][k].first.second].first.first;
                    go_right[i][j][k].first.second = go_right[i - 1][go_right[i - 1][j][k].first.first][go_right[i - 1][j][k].first.second].first.second;
                    go_right[i][j][k].second = max(go_right[i - 1][j][k].second, go_right[i - 1][go_right[i - 1][j][k].first.first][go_right[i - 1][j][k].first.second].second);
                } else {
                    go_right[i][j][k] = make_pair(make_pair(-1, -1), -R);
                }
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        pos[ord[i]] = i;
    }
}

int compare_plants(int x, int y) {
    if (pos[x] > pos[y]) {
        int l = x - k, r = x + k;
        int nw1 = pos[x], nw2 = 0;
        for (int i = lg - 1; i >= 0; --i) {
            if (go_left[i][nw1][nw2].first.first > pos[y]) {
                l = min(l, go_left[i][nw1][nw2].second);
                int nw3 = go_left[i][nw1][nw2].first.first, nw4 = go_left[i][nw1][nw2].first.second;
                nw1 = nw3, nw2 = nw4;
            }
        }
        nw1 = pos[x], nw2 = 0;
        for (int i = lg - 1; i >= 0; --i) {
            if (go_right[i][nw1][nw2].first.first > pos[y]) {
                r = max(r, go_right[i][nw1][nw2].second);
                int nw3 = go_right[i][nw1][nw2].first.first, nw4 = go_right[i][nw1][nw2].first.second;
                nw1 = nw3, nw2 = nw4;
            }
        }
        if ((l < y && y < r) || (l < y - n && y - n < r) || (l < y + n && y + n < r)) {
            return 1;
        }
        return 0;
    } else {
        swap(x, y);
        int l = x - k, r = x + k;
        int nw1 = pos[x], nw2 = 0;
        for (int i = lg - 1; i >= 0; --i) {
            if (go_left[i][nw1][nw2].first.first > pos[y]) {
                l = min(l, go_left[i][nw1][nw2].second);
                int nw3 = go_left[i][nw1][nw2].first.first, nw4 = go_left[i][nw1][nw2].first.second;
                nw1 = nw3, nw2 = nw4;
            }
        }
        nw1 = pos[x], nw2 = 0;
        for (int i = lg - 1; i >= 0; --i) {
            if (go_right[i][nw1][nw2].first.first > pos[y]) {
                r = max(r, go_right[i][nw1][nw2].second);
                int nw3 = go_right[i][nw1][nw2].first.first, nw4 = go_right[i][nw1][nw2].first.second;
                nw1 = nw3, nw2 = nw4;
            }
        }
        if ((l < y && y < r) || (l < y - n && y - n < r) || (l < y + n && y + n < r)) {
            return -1;
        }
        return 0;
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 105820 KB Output is correct
2 Correct 9 ms 105820 KB Output is correct
3 Correct 9 ms 105820 KB Output is correct
4 Correct 8 ms 105820 KB Output is correct
5 Correct 9 ms 105820 KB Output is correct
6 Correct 43 ms 109488 KB Output is correct
7 Correct 96 ms 129856 KB Output is correct
8 Correct 428 ms 219844 KB Output is correct
9 Correct 421 ms 219880 KB Output is correct
10 Correct 467 ms 219768 KB Output is correct
11 Correct 448 ms 219848 KB Output is correct
12 Correct 481 ms 219944 KB Output is correct
13 Correct 537 ms 219760 KB Output is correct
14 Correct 509 ms 220000 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 105816 KB Output is correct
2 Correct 8 ms 105820 KB Output is correct
3 Correct 9 ms 105816 KB Output is correct
4 Correct 8 ms 105820 KB Output is correct
5 Correct 9 ms 105792 KB Output is correct
6 Correct 13 ms 105840 KB Output is correct
7 Correct 73 ms 114692 KB Output is correct
8 Correct 10 ms 105820 KB Output is correct
9 Correct 13 ms 105908 KB Output is correct
10 Correct 74 ms 114808 KB Output is correct
11 Correct 79 ms 114768 KB Output is correct
12 Correct 80 ms 114772 KB Output is correct
13 Correct 72 ms 114672 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 105816 KB Output is correct
2 Correct 8 ms 105820 KB Output is correct
3 Correct 9 ms 105816 KB Output is correct
4 Correct 8 ms 105820 KB Output is correct
5 Correct 9 ms 105792 KB Output is correct
6 Correct 13 ms 105840 KB Output is correct
7 Correct 73 ms 114692 KB Output is correct
8 Correct 10 ms 105820 KB Output is correct
9 Correct 13 ms 105908 KB Output is correct
10 Correct 74 ms 114808 KB Output is correct
11 Correct 79 ms 114768 KB Output is correct
12 Correct 80 ms 114772 KB Output is correct
13 Correct 72 ms 114672 KB Output is correct
14 Correct 127 ms 129796 KB Output is correct
15 Correct 881 ms 220616 KB Output is correct
16 Correct 166 ms 130016 KB Output is correct
17 Correct 884 ms 220640 KB Output is correct
18 Correct 736 ms 220224 KB Output is correct
19 Correct 743 ms 220808 KB Output is correct
20 Correct 867 ms 220652 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 105820 KB Output is correct
2 Correct 8 ms 105792 KB Output is correct
3 Correct 68 ms 110308 KB Output is correct
4 Correct 569 ms 219848 KB Output is correct
5 Correct 605 ms 220048 KB Output is correct
6 Correct 677 ms 220288 KB Output is correct
7 Correct 764 ms 220360 KB Output is correct
8 Correct 871 ms 220648 KB Output is correct
9 Correct 560 ms 219964 KB Output is correct
10 Correct 549 ms 219956 KB Output is correct
11 Correct 550 ms 219976 KB Output is correct
12 Correct 557 ms 220104 KB Output is correct
13 Correct 686 ms 220120 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 105816 KB Output is correct
2 Correct 8 ms 105788 KB Output is correct
3 Correct 9 ms 105912 KB Output is correct
4 Correct 9 ms 105824 KB Output is correct
5 Correct 8 ms 105908 KB Output is correct
6 Correct 11 ms 105824 KB Output is correct
7 Correct 18 ms 106824 KB Output is correct
8 Correct 18 ms 106780 KB Output is correct
9 Correct 19 ms 106844 KB Output is correct
10 Correct 19 ms 106844 KB Output is correct
11 Correct 18 ms 106724 KB Output is correct
12 Correct 19 ms 106836 KB Output is correct
13 Correct 19 ms 106844 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 105820 KB Output is correct
2 Correct 10 ms 105776 KB Output is correct
3 Correct 9 ms 105896 KB Output is correct
4 Correct 9 ms 105816 KB Output is correct
5 Correct 13 ms 105820 KB Output is correct
6 Correct 562 ms 219080 KB Output is correct
7 Correct 658 ms 219336 KB Output is correct
8 Correct 692 ms 219684 KB Output is correct
9 Correct 834 ms 219728 KB Output is correct
10 Correct 516 ms 219080 KB Output is correct
11 Correct 636 ms 219792 KB Output is correct
12 Correct 472 ms 218944 KB Output is correct
13 Correct 565 ms 219244 KB Output is correct
14 Correct 664 ms 219332 KB Output is correct
15 Correct 717 ms 219592 KB Output is correct
16 Correct 452 ms 219112 KB Output is correct
17 Correct 541 ms 219112 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 105820 KB Output is correct
2 Correct 9 ms 105820 KB Output is correct
3 Correct 9 ms 105820 KB Output is correct
4 Correct 8 ms 105820 KB Output is correct
5 Correct 9 ms 105820 KB Output is correct
6 Correct 43 ms 109488 KB Output is correct
7 Correct 96 ms 129856 KB Output is correct
8 Correct 428 ms 219844 KB Output is correct
9 Correct 421 ms 219880 KB Output is correct
10 Correct 467 ms 219768 KB Output is correct
11 Correct 448 ms 219848 KB Output is correct
12 Correct 481 ms 219944 KB Output is correct
13 Correct 537 ms 219760 KB Output is correct
14 Correct 509 ms 220000 KB Output is correct
15 Correct 9 ms 105816 KB Output is correct
16 Correct 8 ms 105820 KB Output is correct
17 Correct 9 ms 105816 KB Output is correct
18 Correct 8 ms 105820 KB Output is correct
19 Correct 9 ms 105792 KB Output is correct
20 Correct 13 ms 105840 KB Output is correct
21 Correct 73 ms 114692 KB Output is correct
22 Correct 10 ms 105820 KB Output is correct
23 Correct 13 ms 105908 KB Output is correct
24 Correct 74 ms 114808 KB Output is correct
25 Correct 79 ms 114768 KB Output is correct
26 Correct 80 ms 114772 KB Output is correct
27 Correct 72 ms 114672 KB Output is correct
28 Correct 127 ms 129796 KB Output is correct
29 Correct 881 ms 220616 KB Output is correct
30 Correct 166 ms 130016 KB Output is correct
31 Correct 884 ms 220640 KB Output is correct
32 Correct 736 ms 220224 KB Output is correct
33 Correct 743 ms 220808 KB Output is correct
34 Correct 867 ms 220652 KB Output is correct
35 Correct 8 ms 105820 KB Output is correct
36 Correct 8 ms 105792 KB Output is correct
37 Correct 68 ms 110308 KB Output is correct
38 Correct 569 ms 219848 KB Output is correct
39 Correct 605 ms 220048 KB Output is correct
40 Correct 677 ms 220288 KB Output is correct
41 Correct 764 ms 220360 KB Output is correct
42 Correct 871 ms 220648 KB Output is correct
43 Correct 560 ms 219964 KB Output is correct
44 Correct 549 ms 219956 KB Output is correct
45 Correct 550 ms 219976 KB Output is correct
46 Correct 557 ms 220104 KB Output is correct
47 Correct 686 ms 220120 KB Output is correct
48 Correct 9 ms 105816 KB Output is correct
49 Correct 8 ms 105788 KB Output is correct
50 Correct 9 ms 105912 KB Output is correct
51 Correct 9 ms 105824 KB Output is correct
52 Correct 8 ms 105908 KB Output is correct
53 Correct 11 ms 105824 KB Output is correct
54 Correct 18 ms 106824 KB Output is correct
55 Correct 18 ms 106780 KB Output is correct
56 Correct 19 ms 106844 KB Output is correct
57 Correct 19 ms 106844 KB Output is correct
58 Correct 18 ms 106724 KB Output is correct
59 Correct 19 ms 106836 KB Output is correct
60 Correct 19 ms 106844 KB Output is correct
61 Correct 57 ms 110420 KB Output is correct
62 Correct 100 ms 129800 KB Output is correct
63 Correct 488 ms 219840 KB Output is correct
64 Correct 552 ms 220136 KB Output is correct
65 Correct 688 ms 220360 KB Output is correct
66 Correct 792 ms 220356 KB Output is correct
67 Correct 826 ms 220600 KB Output is correct
68 Correct 543 ms 219992 KB Output is correct
69 Correct 772 ms 220612 KB Output is correct
70 Correct 521 ms 220104 KB Output is correct
71 Correct 603 ms 220104 KB Output is correct
72 Correct 703 ms 220212 KB Output is correct
73 Correct 759 ms 220476 KB Output is correct
74 Correct 478 ms 219868 KB Output is correct
75 Correct 594 ms 220352 KB Output is correct