Submission #1057140

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057140		arbuzick	Comparing Plants (IOI20_plants)	C++17	100 / 100	884 ms	220808 KiB

plants

#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 / 5
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 11 / 11
• Subtask 6: 15 / 15
• Subtask 7: 25 / 25