oj.uz

Submission #835057

# Submission time Handle Problem Language Result Execution time Memory
835057 2023-08-23T07:19:13 Z finn__ Comparing Plants (IOI20_plants) C++17
100 / 100
 955 ms 138912 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 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 <= n)
        {
            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 <= n)
        {
            right_jmp[0][i][0] = min_index;
            right_jmp[0][i][1] = cyclic_distance(i, min_index, 0);
        }
        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 (cyclic_distance(x, y, 1) < k || cyclic_distance(x, y, 0) < k)
        return h[x] > h[y] ? 1 : -1;
    return is_less(x, y) ? -1 : (is_less(y, x) ? 1 : 0);
}

Compilation message

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:167:23: warning: comparison of integer expressions of different signedness: 'std::tuple_element<1, std::pair<long unsigned int, long int> >::type' {aka 'long int'} and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
  167 |         if (min_value <= n)
      |             ~~~~~~~~~~^~~~
plants.cpp:179:23: warning: comparison of integer expressions of different signedness: 'std::tuple_element<1, std::pair<long unsigned int, long int> >::type' {aka 'long int'} and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
  179 |         if (min_value <= n)
      |             ~~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12884 KB Output is correct
2 Correct 6 ms 12884 KB Output is correct
3 Correct 6 ms 12884 KB Output is correct
4 Correct 6 ms 12884 KB Output is correct
5 Correct 6 ms 12884 KB Output is correct
6 Correct 55 ms 16588 KB Output is correct
7 Correct 150 ms 29392 KB Output is correct
8 Correct 484 ms 135244 KB Output is correct
9 Correct 521 ms 135260 KB Output is correct
10 Correct 576 ms 135212 KB Output is correct
11 Correct 635 ms 135312 KB Output is correct
12 Correct 649 ms 135220 KB Output is correct
13 Correct 730 ms 135172 KB Output is correct
14 Correct 663 ms 135272 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12884 KB Output is correct
2 Correct 5 ms 12884 KB Output is correct
3 Correct 6 ms 12884 KB Output is correct
4 Correct 6 ms 12884 KB Output is correct
5 Correct 6 ms 12884 KB Output is correct
6 Correct 12 ms 13524 KB Output is correct
7 Correct 65 ms 20488 KB Output is correct
8 Correct 10 ms 13012 KB Output is correct
9 Correct 9 ms 13524 KB Output is correct
10 Correct 60 ms 20556 KB Output is correct
11 Correct 56 ms 20432 KB Output is correct
12 Correct 56 ms 20684 KB Output is correct
13 Correct 61 ms 20532 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12884 KB Output is correct
2 Correct 5 ms 12884 KB Output is correct
3 Correct 6 ms 12884 KB Output is correct
4 Correct 6 ms 12884 KB Output is correct
5 Correct 6 ms 12884 KB Output is correct
6 Correct 12 ms 13524 KB Output is correct
7 Correct 65 ms 20488 KB Output is correct
8 Correct 10 ms 13012 KB Output is correct
9 Correct 9 ms 13524 KB Output is correct
10 Correct 60 ms 20556 KB Output is correct
11 Correct 56 ms 20432 KB Output is correct
12 Correct 56 ms 20684 KB Output is correct
13 Correct 61 ms 20532 KB Output is correct
14 Correct 99 ms 29516 KB Output is correct
15 Correct 788 ms 136020 KB Output is correct
16 Correct 102 ms 29484 KB Output is correct
17 Correct 792 ms 136052 KB Output is correct
18 Correct 427 ms 135660 KB Output is correct
19 Correct 424 ms 136220 KB Output is correct
20 Correct 721 ms 136056 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12884 KB Output is correct
2 Correct 6 ms 12884 KB Output is correct
3 Correct 98 ms 16848 KB Output is correct
4 Correct 755 ms 138600 KB Output is correct
5 Correct 769 ms 135672 KB Output is correct
6 Correct 909 ms 135628 KB Output is correct
7 Correct 905 ms 135752 KB Output is correct
8 Correct 766 ms 135968 KB Output is correct
9 Correct 719 ms 135524 KB Output is correct
10 Correct 777 ms 135336 KB Output is correct
11 Correct 735 ms 135176 KB Output is correct
12 Correct 771 ms 135444 KB Output is correct
13 Correct 619 ms 135416 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 13008 KB Output is correct
2 Correct 6 ms 12884 KB Output is correct
3 Correct 6 ms 12884 KB Output is correct
4 Correct 6 ms 12884 KB Output is correct
5 Correct 6 ms 12884 KB Output is correct
6 Correct 8 ms 13012 KB Output is correct
7 Correct 21 ms 14036 KB Output is correct
8 Correct 17 ms 14036 KB Output is correct
9 Correct 25 ms 14036 KB Output is correct
10 Correct 18 ms 14036 KB Output is correct
11 Correct 22 ms 14028 KB Output is correct
12 Correct 21 ms 14036 KB Output is correct
13 Correct 16 ms 14036 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12884 KB Output is correct
2 Correct 6 ms 12884 KB Output is correct
3 Correct 6 ms 12884 KB Output is correct
4 Correct 6 ms 12884 KB Output is correct
5 Correct 8 ms 13524 KB Output is correct
6 Correct 595 ms 134604 KB Output is correct
7 Correct 684 ms 134788 KB Output is correct
8 Correct 796 ms 134916 KB Output is correct
9 Correct 728 ms 135084 KB Output is correct
10 Correct 536 ms 134732 KB Output is correct
11 Correct 554 ms 135084 KB Output is correct
12 Correct 566 ms 138348 KB Output is correct
13 Correct 647 ms 134856 KB Output is correct
14 Correct 714 ms 134724 KB Output is correct
15 Correct 747 ms 134876 KB Output is correct
16 Correct 462 ms 134400 KB Output is correct
17 Correct 542 ms 134604 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12884 KB Output is correct
2 Correct 6 ms 12884 KB Output is correct
3 Correct 6 ms 12884 KB Output is correct
4 Correct 6 ms 12884 KB Output is correct
5 Correct 6 ms 12884 KB Output is correct
6 Correct 55 ms 16588 KB Output is correct
7 Correct 150 ms 29392 KB Output is correct
8 Correct 484 ms 135244 KB Output is correct
9 Correct 521 ms 135260 KB Output is correct
10 Correct 576 ms 135212 KB Output is correct
11 Correct 635 ms 135312 KB Output is correct
12 Correct 649 ms 135220 KB Output is correct
13 Correct 730 ms 135172 KB Output is correct
14 Correct 663 ms 135272 KB Output is correct
15 Correct 6 ms 12884 KB Output is correct
16 Correct 5 ms 12884 KB Output is correct
17 Correct 6 ms 12884 KB Output is correct
18 Correct 6 ms 12884 KB Output is correct
19 Correct 6 ms 12884 KB Output is correct
20 Correct 12 ms 13524 KB Output is correct
21 Correct 65 ms 20488 KB Output is correct
22 Correct 10 ms 13012 KB Output is correct
23 Correct 9 ms 13524 KB Output is correct
24 Correct 60 ms 20556 KB Output is correct
25 Correct 56 ms 20432 KB Output is correct
26 Correct 56 ms 20684 KB Output is correct
27 Correct 61 ms 20532 KB Output is correct
28 Correct 99 ms 29516 KB Output is correct
29 Correct 788 ms 136020 KB Output is correct
30 Correct 102 ms 29484 KB Output is correct
31 Correct 792 ms 136052 KB Output is correct
32 Correct 427 ms 135660 KB Output is correct
33 Correct 424 ms 136220 KB Output is correct
34 Correct 721 ms 136056 KB Output is correct
35 Correct 6 ms 12884 KB Output is correct
36 Correct 6 ms 12884 KB Output is correct
37 Correct 98 ms 16848 KB Output is correct
38 Correct 755 ms 138600 KB Output is correct
39 Correct 769 ms 135672 KB Output is correct
40 Correct 909 ms 135628 KB Output is correct
41 Correct 905 ms 135752 KB Output is correct
42 Correct 766 ms 135968 KB Output is correct
43 Correct 719 ms 135524 KB Output is correct
44 Correct 777 ms 135336 KB Output is correct
45 Correct 735 ms 135176 KB Output is correct
46 Correct 771 ms 135444 KB Output is correct
47 Correct 619 ms 135416 KB Output is correct
48 Correct 5 ms 13008 KB Output is correct
49 Correct 6 ms 12884 KB Output is correct
50 Correct 6 ms 12884 KB Output is correct
51 Correct 6 ms 12884 KB Output is correct
52 Correct 6 ms 12884 KB Output is correct
53 Correct 8 ms 13012 KB Output is correct
54 Correct 21 ms 14036 KB Output is correct
55 Correct 17 ms 14036 KB Output is correct
56 Correct 25 ms 14036 KB Output is correct
57 Correct 18 ms 14036 KB Output is correct
58 Correct 22 ms 14028 KB Output is correct
59 Correct 21 ms 14036 KB Output is correct
60 Correct 16 ms 14036 KB Output is correct
61 Correct 94 ms 18556 KB Output is correct
62 Correct 161 ms 29356 KB Output is correct
63 Correct 624 ms 135264 KB Output is correct
64 Correct 707 ms 135520 KB Output is correct
65 Correct 908 ms 135676 KB Output is correct
66 Correct 878 ms 135788 KB Output is correct
67 Correct 784 ms 135992 KB Output is correct
68 Correct 774 ms 135728 KB Output is correct
69 Correct 613 ms 135996 KB Output is correct
70 Correct 827 ms 138912 KB Output is correct
71 Correct 955 ms 135680 KB Output is correct
72 Correct 923 ms 135636 KB Output is correct
73 Correct 910 ms 135756 KB Output is correct
74 Correct 596 ms 135304 KB Output is correct
75 Correct 686 ms 135500 KB Output is correct