Submission #835052

#	Time	Username	Problem	Language	Result	Execution time	Memory
835052		finn__	Comparing Plants (IOI20_plants)	C++17	0 / 100	98 ms	17144 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 update_point(size_t i, int64_t x, size_t k = 1, size_t a = 0, size_t b = L - 1)
    {
        if (a == b)
        {
            t[k].min_value = x;
            return;
        }

        propagate(k);
        if (i <= (a + b) / 2)
            update_point(i, x, k << 1, a, (a + b) / 2);
        else
            update_point(i, x, 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, LGN = 18, L = 1 << LGN;

size_t n, k, h[N], curr_rank, left_jmp[LGN][N][2], right_jmp[LGN][N][2];
segtree<L> tree;

size_t cyclic_distance(size_t i, size_t j, bool goes_left)
{
    if (goes_left)
    {
        if (i >= j)
            return i - j;
        return n - j + i;
    }
    else
    {
        if (i <= j)
            return j - i;
        return n - i + j;
    }
}

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.update_point(i, INT64_MAX);
    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);

    // reuse segment tree for storing heights
    vector<size_t> plants(n);
    iota(plants.begin(), plants.end(), 0);
    sort(plants.begin(), plants.end(), [&](size_t const &a, size_t const &b)
         { return h[a] > h[b]; });

    for (size_t i = 0; i < L; ++i)
        tree.t[i].lazy = 0;

    for (size_t const &i : plants)
    {
        auto [min_index, min_value] = tree.cyclic_argmin((i - k + 1 + n) % n, (i - 1 + n) % n, n);
        if (min_value != INT64_MAX)
        {
            left_jmp[0][i][0] = min_index;
            left_jmp[0][i][1] = cyclic_distance(i, min_index, 1);
        }
        else
        {
            left_jmp[0][i][0] = n;
            left_jmp[0][i][1] = UINT32_MAX;
        }

        tie(min_index, min_value) = tree.cyclic_argmin((i + 1) % n, (i + k - 1) % n, n);
        if (min_value != INT64_MAX)
        {
            right_jmp[0][i][0] = min_index;
            right_jmp[0][i][1] = cyclic_distance(i, min_index, 1);
        }
        else
        {
            right_jmp[0][i][0] = n;
            right_jmp[0][i][1] = UINT32_MAX;
        }

        tree.update_point(i, h[i]);
    }

    left_jmp[0][n][0] = n;
    right_jmp[0][n][0] = n;

    for (size_t j = 1; j < LGN; ++j)
        for (size_t i = 0; i < n; ++i)
        {
            left_jmp[j][i][0] = left_jmp[j - 1][left_jmp[j - 1][i][0]][0];
            left_jmp[j][i][1] = left_jmp[j - 1][i][1] + left_jmp[j - 1][left_jmp[j - 1][i][0]][1];
            right_jmp[j][i][0] = right_jmp[j - 1][right_jmp[j - 1][i][0]][0];
            right_jmp[j][i][1] = right_jmp[j - 1][i][1] + right_jmp[j - 1][right_jmp[j - 1][i][0]][1];
        }
}

bool is_less(size_t x, size_t y)
{
    size_t u = x, d = cyclic_distance(x, y, 1);
    for (size_t i = LGN - 1; i < LGN; --i)
        if (left_jmp[i][u][1] <= d)
            d -= left_jmp[i][u][1], u = left_jmp[i][u][0];
    if (d >= k)
        u = left_jmp[0][u][0];
    if (u != n && h[u] < h[y])
        return 1;

    u = x, d = cyclic_distance(x, y, 0);
    for (size_t i = LGN - 1; i < LGN; --i)
        if (right_jmp[i][u][1] <= d)
            d -= right_jmp[i][u][1], u = right_jmp[i][u][0];
    if (d >= k)
        u = right_jmp[0][u][0];
    if (u != n && h[u] < h[y])
        return 1;

    return 0;
}

int compare_plants(int x, int y)
{
    if (abs(x - y) < k)
        return h[x] > h[y] ? 1 : -1;
    return is_less(x, y) ? -1 : (is_less(y, x) ? 1 : 0);
}

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