Submission #1178659

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178659		Mans21	Comparing Plants (IOI20_plants)	C++20	30 / 100	1045 ms	78080 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
#define ent '\n'

const int maxn = 5e5 + 12;
using namespace std;

int r[maxn], a[maxn];
pair<int, int> t[maxn * 4];
int p[maxn * 4];
int del[maxn], add[maxn];
int n, k;

void build(int v, int tl, int tr) {
    if(tl == tr) {
        t[v] = {r[tl], tl};
        return;
    }
    int mid = (tl + tr) >> 1;
    build(v * 2, tl, mid);
    build(v * 2 + 1, mid + 1, tr);
    t[v] = min(t[v * 2], t[v * 2 + 1]);
}

void push(int v, int tl, int tr) {
    if(tl == tr) return;
    t[v * 2].first += p[v];
    t[v * 2 + 1].first += p[v];
    p[v * 2] += p[v], p[v * 2 + 1] += p[v];
    p[v] = 0;
}

void upd(int v, int tl, int tr, int l, int r, int x) {
    if(tl > r || l > tr) return;
    if(tl >= l && tr <= r) {
        t[v].first += x;
        p[v] += x;
        return;
    }
    push(v, tl, tr);
    int mid = (tl + tr) >> 1;
    upd(v * 2, tl, mid, l, r, x);
    upd(v * 2 + 1, mid + 1, tr, l, r, x);
    t[v] = min(t[v * 2], t[v * 2 + 1]);
}

void upd(int l, int r, int x) {
    l %= n, r %= n;
    if(l < 0) l += n;
    if(r < 0) r += n;

    if(l <= r) {
        upd(1, 0, n - 1, l, r, x);
    }
    else {
        upd(1, 0, n - 1, l, n - 1, x);
        upd(1, 0, n - 1, 0, r, x);
    }
}

pair<int, int> get(int v, int tl, int tr, int l, int r) {
    if(tl > r || l > tr) return {1e9, 0};
    if(tl >= l && tr <= r) return t[v];
    push(v, tl, tr);
    int mid = (tl + tr) >> 1;
    return min(get(v * 2, tl, mid, l, r), get(v * 2 + 1, mid + 1, tr, l, r));
}

pair<int, int> get(int l, int r) {
    l %= n, r %= n;
    if(l < 0) l += n;
    if(r < 0) r += n;

    if(l <= r) {
        return get(1, 0, n - 1, l, r);
    }
    return min(get(1, 0, n - 1, l, n - 1), get(1, 0, n - 1, 0, r));
}

int pl[maxn], pr[maxn];
int position[maxn];

void apply(int pos, int &_) {
    while(get(pos - k + 1 , pos - 1).first == 0) {
        apply(get(pos - k + 1 , pos - 1).second, _);
    }
    a[pos] = --_;
    position[a[pos]] = pos;

    upd(pos, pos, 1e9);
    upd(pos - k + 1, pos - 1, -1);
}


int upl[20][maxn], upr[20][maxn];
int sl[20][maxn], sr[20][maxn];

void init(int K, std::vector<int> R) {
    k = K;
    n = (int)R.size();
    for(int i = 0; i < n; i++) {
        r[i] = R[i];
    }

    build(1, 0, n - 1);

    int _ = n;
    while(_ > 0) {
        apply(t[1].second, _);
    }

    for(int i = 0; i < n; i++) {
        upd(i, i, -get(i, i).first);
        upd(i, i, 1e9);
    }

    for(int j = 0; j < n; j++) {
        int i = position[j];
        auto [lval, le] = get(i - k + 1, i);
        auto [rval, ri] = get(i, i + k - 1);
        pl[i] = pr[i] = -1;

        if(lval <= 0) pl[i] = le;
        if(rval <= 0) pr[i] = ri;

        upd(i, i, -a[i] - get(i, i).first);
    }

    auto len = [&](int l, int r) -> int {
        if(l <= r) return r - l;
        return r + n - l;
    };

    for(int i = 0; i < n; i++) {
        upl[0][i] = pl[i];
        sl[0][i] = len(pl[i], i);

        upr[0][i] = pr[i];
        sr[0][i] = len(i, pr[i]);
    }

    for(int k = 1; k < 20; k++) {
        for(int i = 0; i < n; i++) {
            if(upl[k - 1][i] == -1) {
                upl[k][i] = -1;
                sl[k][i] = sl[k - 1][i];
            }
            else {
                upl[k][i] = upl[k - 1][upl[k - 1][i]];
                sl[k][i] = sl[k - 1][upl[k - 1][i]] + sl[k - 1][i];
            }

            if(upr[k - 1][i] == -1) {
                upr[k][i] = -1;
                sr[k][i] = sr[k - 1][i];
            }
            else {
                upr[k][i] = upr[k - 1][upr[k - 1][i]];
                sr[k][i] = sr[k - 1][i] + sr[k - 1][upr[k - 1][i]];
            }
        }
    }
}

bool check(int l, int r, int x) {
    l %= n, r %= n;
    if(l < 0) l += n;
    if(r < 0) r += n;

    if(l <= r) return (l <= x && x <= r);
    return (x <= r || x >= l);
}

bool check(int x, int y) {
    int z = x, len = 1;
    for(int i = 19; i >= 0; i--) {
        if(upr[i][z] != -1 && !check(x, upr[i][z], y) && len + sr[i][z] < n) {
            len += sr[i][z];
            z = upr[i][z];
        }
    }
    assert(z != y);
    if(upr[0][z] != -1 && (check(x, upr[0][z], y) || len + sr[0][z] >= n) && a[z] > a[y]) {
        return true;
    }

    z = x, len = 1;
    for(int i = 19; i >= 0; i--) {
        if(upl[i][z] != -1 && !check(upl[i][z], x, y) && len + sl[i][z] < n) {
            len += sl[i][z];
            z = upl[i][z];
        }
    }

    assert(z != y);
    if(upl[0][z] != -1 && (check(upl[0][z], x, y) || len + sl[0][z] >= n) && a[z] > a[y]) {
        return true;
    }

    return false;
}

int compare_plants(int x, int y) {
    if(check(y, x)) return -1;
    if(check(x, y)) return 1;
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 11 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25