Submission #834889

#	Time	Username	Problem	Language	Result	Execution time	Memory
834889		finn__	Comparing Plants (IOI20_plants)	C++17	44 / 100	379 ms	24952 KiB

plants

#include <bits/stdc++.h>

#include "plants.h"

using namespace std;

template <size_t L>
struct segtree
{
    struct node
    {
        int64_t min_value, lazy;
        size_t min_index;
        node() { min_value = INT64_MAX; }
    };

    node t[L << 1];

    node combine(node const &a, node const &b)
    {
        node z;
        z.lazy = 0;
        z.min_value = min(a.min_value, b.min_value);
        z.min_index = a.min_value == z.min_value ? a.min_index : b.min_index;
        return z;
    }

    void build()
    {
        for (size_t i = L; i < L << 1; ++i)
            t[i].min_index = i - L;
        for (size_t i = L - 1; i; --i)
            t[i] = combine(t[i << 1], t[i << 1 | 1]);
    }

    void propagate(size_t k)
    {
        t[k << 1].lazy += t[k].lazy;
        t[k << 1].min_value += t[k].lazy;
        t[k << 1 | 1].lazy += t[k].lazy;
        t[k << 1 | 1].min_value += t[k].lazy;
        t[k].lazy = 0;
    }

    void delete_point(size_t i, size_t k = 1, size_t a = 0, size_t b = L - 1)
    {
        if (a == b)
        {
            t[k].min_value = INT64_MAX;
            return;
        }

        propagate(k);
        if (i <= (a + b) / 2)
            delete_point(i, k << 1, a, (a + b) / 2);
        else
            delete_point(i, k << 1 | 1, (a + b) / 2 + 1, b);
        t[k] = combine(t[k << 1], t[k << 1 | 1]);
    }

    void decrement(size_t i, size_t j, size_t k = 1, size_t a = 0, size_t b = L - 1)
    {
        if (b < i || a > j)
            return;
        if (i <= a && b <= j)
        {
            t[k].lazy--;
            t[k].min_value--;
        }
        else
        {
            propagate(k);
            decrement(i, j, k << 1, a, (a + b) / 2);
            decrement(i, j, k << 1 | 1, (a + b) / 2 + 1, b);
            t[k] = combine(t[k << 1], t[k << 1 | 1]);
        }
    }

    void cyclic_decrement(size_t i, size_t j, size_t n)
    {
        if (i <= j)
            decrement(i, j);
        else
            decrement(i, n - 1), decrement(0, j);
    }

    node argmin(size_t i, size_t j, size_t k = 1, size_t a = 0, size_t b = L - 1)
    {
        if (b < i || a > j)
            return node();
        if (i <= a && b <= j)
            return t[k];
        propagate(k);
        return combine(argmin(i, j, k << 1, a, (a + b) / 2),
                       argmin(i, j, k << 1 | 1, (a + b) / 2 + 1, b));
    }

    pair<size_t, int64_t> cyclic_argmin(size_t i, size_t j, size_t n)
    {
        node ans;
        if (i <= j)
            ans = argmin(i, j);
        else
            ans = combine(argmin(i, n - 1), argmin(0, j));
        return {ans.min_index, ans.min_value};
    }
};

constexpr size_t N = 200000, L = 1 << 18;

size_t n, k, h[N], curr_rank;
segtree<L> tree;

void rank_plant(size_t i)
{
    auto [lowest, val] = tree.cyclic_argmin((i - k + 1 + n) % n, (i - 1 + n) % n, n);
    while (!val)
    {
        rank_plant(lowest);
        tie(lowest, val) = tree.cyclic_argmin((i - k + 1 + n) % n, (i - 1 + n) % n, n);
    }
    h[i] = curr_rank--;
    tree.delete_point(i);
    tree.cyclic_decrement((i - k + 1 + n) % n, (i - 1 + n) % n, n);
}

void init(int k_, std::vector<int> r)
{
    k = k_;
    n = r.size();
    for (size_t i = 0; i < n; ++i)
        tree.t[L + i].min_value = r[i];
    tree.build();

    curr_rank = n;
    while (curr_rank)
        rank_plant(tree.argmin(0, n - 1).min_index);
}

int compare_plants(int x, int y)
{
    return h[x] > h[y] ? 1 : -1;
}

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