oj.uz

Submission #834887

# Submission time Handle Problem Language Result Execution time Memory
834887 2023-08-22T22:22:53 Z finn__ Comparing Plants (IOI20_plants) C++17
0 / 100
 48 ms 15496 KB 
#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 < r.size(); ++i)
        tree.t[L + i].min_value = r[i];
    tree.build();

    curr_rank = n;
    for (size_t i = 0; i < n; ++i)
        if (!h[i] && !tree.argmin(i, i).min_value)
            rank_plant(i);
}

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12500 KB Output is correct
2 Correct 6 ms 12628 KB Output is correct
3 Correct 6 ms 12500 KB Output is correct
4 Incorrect 6 ms 12628 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12500 KB Output is correct
2 Correct 6 ms 12500 KB Output is correct
3 Correct 6 ms 12500 KB Output is correct
4 Incorrect 6 ms 12500 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12500 KB Output is correct
2 Correct 6 ms 12500 KB Output is correct
3 Correct 6 ms 12500 KB Output is correct
4 Incorrect 6 ms 12500 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12500 KB Output is correct
2 Correct 6 ms 12620 KB Output is correct
3 Incorrect 48 ms 15496 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12552 KB Output is correct
2 Correct 6 ms 12500 KB Output is correct
3 Incorrect 6 ms 12500 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12500 KB Output is correct
2 Correct 6 ms 12620 KB Output is correct
3 Incorrect 6 ms 12500 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12500 KB Output is correct
2 Correct 6 ms 12628 KB Output is correct
3 Correct 6 ms 12500 KB Output is correct
4 Incorrect 6 ms 12628 KB Output isn't correct
5 Halted 0 ms 0 KB -