oj.uz

Submission #834889

# Submission time Handle Problem Language Result Execution time Memory
834889 2023-08-22T22:33:38 Z finn__ Comparing Plants (IOI20_plants) C++17
44 / 100
 379 ms 24952 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 < 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.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 #2
14.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 Correct 6 ms 12500 KB Output is correct
5 Correct 7 ms 12628 KB Output is correct
6 Correct 8 ms 12628 KB Output is correct
7 Correct 54 ms 17356 KB Output is correct
8 Correct 7 ms 12628 KB Output is correct
9 Correct 8 ms 12628 KB Output is correct
10 Correct 52 ms 17356 KB Output is correct
11 Correct 50 ms 17288 KB Output is correct
12 Correct 49 ms 17540 KB Output is correct
13 Correct 52 ms 17324 KB Output is correct

Subtask #3
13.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 Correct 6 ms 12500 KB Output is correct
5 Correct 7 ms 12628 KB Output is correct
6 Correct 8 ms 12628 KB Output is correct
7 Correct 54 ms 17356 KB Output is correct
8 Correct 7 ms 12628 KB Output is correct
9 Correct 8 ms 12628 KB Output is correct
10 Correct 52 ms 17356 KB Output is correct
11 Correct 50 ms 17288 KB Output is correct
12 Correct 49 ms 17540 KB Output is correct
13 Correct 52 ms 17324 KB Output is correct
14 Correct 73 ms 17964 KB Output is correct
15 Correct 374 ms 21808 KB Output is correct
16 Correct 73 ms 17996 KB Output is correct
17 Correct 379 ms 21808 KB Output is correct
18 Correct 225 ms 21308 KB Output is correct
19 Correct 234 ms 21856 KB Output is correct
20 Correct 349 ms 21832 KB Output is correct

Subtask #4
17.0 / 17.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 47 ms 15436 KB Output is correct
4 Correct 188 ms 24952 KB Output is correct
5 Correct 218 ms 21452 KB Output is correct
6 Correct 283 ms 21456 KB Output is correct
7 Correct 334 ms 21576 KB Output is correct
8 Correct 343 ms 21708 KB Output is correct
9 Correct 202 ms 21284 KB Output is correct
10 Correct 192 ms 21068 KB Output is correct
11 Correct 156 ms 20948 KB Output is correct
12 Correct 182 ms 21144 KB Output is correct
13 Correct 226 ms 21228 KB Output is correct

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12500 KB Output is correct
2 Correct 5 ms 12628 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 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 -