oj.uz

Submission #569514

# Submission time Handle Problem Language Result Execution time Memory
569514 2022-05-27T12:52:04 Z hoanghq2004 Comparing Plants (IOI20_plants) C++14
100 / 100
 958 ms 56092 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "plants.h"
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 2e5 + 10;

int n;
int p[N];
int lft[N][20], rgt[N][20];

struct node {
    int minval;
    int maxid, minid;
    int lazy;
    node() {
        minval = 1e9;
        maxid = minid = -1;
    }
    node operator + (const node& other) const {
        node ret;
        if (minval < other.minval) {
            ret = *this;
            ret.lazy = 0;
        } else if (minval > other.minval) {
            ret = other;
            ret.lazy = 0;
        } else {
            ret.minval = minval;
            ret.maxid = other.maxid;
            ret.minid = minid;
            ret.lazy = 0;
        }
        return ret;
    }
} st[N * 4];


void push(int id, int delta) {
    st[id].lazy += delta;
    st[id].minval += delta;
}

void update(int id, int L, int R, int i, int val) {
    if (L == R) {
        st[id].minval = val;
        st[id].maxid = st[id].minid = L;
        return;
    }
    int mid = L + R >> 1;
    push(id * 2, st[id].lazy);
    push(id * 2 + 1, st[id].lazy);
    st[id].lazy = 0;
    if (i <= mid) update(id * 2, L, mid, i, val);
    else update(id * 2 + 1, mid + 1, R, i, val);
    st[id] = st[id * 2] + st[id * 2 + 1];
}

void add(int id, int L, int R, int u, int v, int delta) {
    if (u > R || L > v) return;
    if (u <= L && R <= v) {
        push(id, delta);
        return;
    }
    int mid = L + R >> 1;
    push(id * 2, st[id].lazy);
    push(id * 2 + 1, st[id].lazy);
    st[id].lazy = 0;
    add(id * 2, L, mid, u, v, delta);
    add(id * 2 + 1, mid + 1, R, u, v, delta);
    st[id] = st[id * 2] + st[id * 2 + 1];
}

node get(int id, int L, int R, int u, int v) {
    if (u > R || L > v) return node();
    if (u <= L && R <= v) return st[id];
    int mid = L + R >> 1;
    push(id * 2, st[id].lazy);
    push(id * 2 + 1, st[id].lazy);
    st[id].lazy = 0;
    return get(id * 2, L, mid, u, v) + get(id * 2 + 1, mid + 1, R, u, v);
}

int dist(int x, int y) {
    return (y - x + n) % n;
}

void init(int k, vector<int> r) {
    n = r.size();
    for (int i = 0; i < n; ++i) update(1, 0, n - 1, i, r[i]);

    auto check = [&](int i) {
        if (get(1, 0, n - 1, i, i).minval > 0) return 0;
        if (i - k + 1 < 0) {
            if (get(1, 0, n - 1, 0, i - 1).minval <= 0) return 0;
            if (get(1, 0, n - 1, (i - k + 1 + n) % n, n - 1).minval <= 0) return 0;
            return 1;
        } else {
            if (get(1, 0, n - 1, i - k + 1, i - 1).minval <= 0) return 0;
            return 1;
        }
    };
    auto get_next = [&](int u) {
        if (st[1].minval > 0) return -1;
        node cur = get(1, 0, n - 1, u, n - 1);
        if (cur.minval <= 0) return cur.minid;
        cur = get(1, 0, n - 1, 0, u - 1);
        if (cur.minval <= 0) return cur.minid;
        return -1;
    };
    auto get_prev = [&](int u) {
        if (st[1].minval > 0) return -1;
        node cur = get(1, 0, n - 1, 0, u - 1);
        if (cur.minval <= 0) return cur.maxid;
        cur = get(1, 0, n - 1, u, n - 1);
        if (cur.minval <= 0) return cur.maxid;
        return -1;
    };
    int m = n;
    auto add_range = [&](int i, int k) {
        if (i - k + 1 < 0) {
            if (i != 0) add(1, 0, n - 1, 0, i - 1, -1);
            add(1, 0, n - 1, (i - k + 1 + n) % n, n - 1, -1);
        } else {
            add(1, 0, n - 1, i - k + 1, i - 1, -1);
        }
    };
    function <void(int)> dfs = [&](int u) {
        while (1) {
            int v = get_prev(u);
            if (v != u && dist(v, u) + 1 <= k) {
                dfs(v);
            }
            else break;
        }
        p[u] = --m;
        add_range(u, k);
        update(1, 0, n - 1, u, 1e9);
    };
    while (st[1].minval <= 0) {
        int i = st[1].minid;
        dfs(i);
    }
    for (int i = 0; i < N * 4; ++i) st[i] = node();
    vector <int> s(n);
    for (int i = 0; i < n; ++i) s[p[i]] = i;
    for (int id = 0; id < n; ++id) {
        int i = s[id];
        if (i - k + 1 >= 0) {
            lft[i][0] = get(1, 0, n - 1, i - k + 1, i - 1).minid;
        } else {
            lft[i][0] = (get(1, 0, n - 1, 0, i - 1) + get(1, 0, n - 1, (i - k + 1 + n) % n, n - 1)).minid;
        }
        if (i + k - 1 < n) {
            rgt[i][0] = get(1, 0, n - 1, i + 1, i + k - 1).minid;
        } else {
            rgt[i][0] = (get(1, 0, n - 1, i + 1, n - 1) + get(1, 0, n - 1, 0, (i + k - 1) % n)).minid;
        }
        update(1, 0, n - 1, i, - p[i]);
    }
    for (int i = 0; i < n; ++i) {
        if (lft[i][0] == -1) lft[i][0] = i;
        if (rgt[i][0] == -1) rgt[i][0] = i;
        lft[i][0] = dist(lft[i][0], i);
        rgt[i][0] = dist(i, rgt[i][0]);
    }

    for (int lg = 1; lg < 20; ++lg) {
        for (int i = 0; i < n; ++i) {
            lft[i][lg] = min(lft[i][lg - 1] + lft[(i - lft[i][lg - 1] % n + n) % n][lg - 1], n);
            rgt[i][lg] = min(rgt[i][lg - 1] + rgt[(i + rgt[i][lg - 1]) % n][lg - 1], n);
        }
    }
}


int reachable(int x, int y) {
    int w = x;
    for (int i = 19; i >= 0; --i)
        if (dist(w, x) + lft[w][i] < dist(y, x)) {
            w = (w - lft[w][i] % n + n) % n;
        }

    if (lft[w][0] && p[w] > p[y]) return 1;
    w = x;
    for (int i = 19; i >= 0; --i)
        if (dist(x, w) + rgt[w][i] < dist(x, y)) {
            w = (w + rgt[w][i]) % n;
        }
    if (rgt[w][0] && p[w] > p[y]) return 1;
    return 0;
}


int compare_plants(int x, int y) {
    if (reachable(x, y)) return 1;
    if (reachable(y, x)) return -1;
    return 0;
}

Compilation message

plants.cpp: In function 'void update(int, int, int, int, int)':
plants.cpp:57:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |     int mid = L + R >> 1;
      |               ~~^~~
plants.cpp: In function 'void add(int, int, int, int, int, int)':
plants.cpp:72:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |     int mid = L + R >> 1;
      |               ~~^~~
plants.cpp: In function 'node get(int, int, int, int, int)':
plants.cpp:84:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |     int mid = L + R >> 1;
      |               ~~^~~
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:99:10: warning: variable 'check' set but not used [-Wunused-but-set-variable]
   99 |     auto check = [&](int i) {
      |          ^~~~~
plants.cpp:110:10: warning: variable 'get_next' set but not used [-Wunused-but-set-variable]
  110 |     auto get_next = [&](int u) {
      |          ^~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12756 KB Output is correct
2 Correct 8 ms 12756 KB Output is correct
3 Correct 8 ms 12756 KB Output is correct
4 Correct 8 ms 12756 KB Output is correct
5 Correct 8 ms 12832 KB Output is correct
6 Correct 203 ms 16664 KB Output is correct
7 Correct 270 ms 21276 KB Output is correct
8 Correct 620 ms 52724 KB Output is correct
9 Correct 623 ms 52448 KB Output is correct
10 Correct 627 ms 52592 KB Output is correct
11 Correct 653 ms 52536 KB Output is correct
12 Correct 665 ms 52556 KB Output is correct
13 Correct 636 ms 52548 KB Output is correct
14 Correct 700 ms 52656 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12776 KB Output is correct
2 Correct 8 ms 12836 KB Output is correct
3 Correct 9 ms 12796 KB Output is correct
4 Correct 8 ms 12756 KB Output is correct
5 Correct 9 ms 12844 KB Output is correct
6 Correct 13 ms 13056 KB Output is correct
7 Correct 122 ms 18364 KB Output is correct
8 Correct 11 ms 12852 KB Output is correct
9 Correct 13 ms 13108 KB Output is correct
10 Correct 122 ms 18400 KB Output is correct
11 Correct 150 ms 18336 KB Output is correct
12 Correct 205 ms 18528 KB Output is correct
13 Correct 124 ms 18344 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12776 KB Output is correct
2 Correct 8 ms 12836 KB Output is correct
3 Correct 9 ms 12796 KB Output is correct
4 Correct 8 ms 12756 KB Output is correct
5 Correct 9 ms 12844 KB Output is correct
6 Correct 13 ms 13056 KB Output is correct
7 Correct 122 ms 18364 KB Output is correct
8 Correct 11 ms 12852 KB Output is correct
9 Correct 13 ms 13108 KB Output is correct
10 Correct 122 ms 18400 KB Output is correct
11 Correct 150 ms 18336 KB Output is correct
12 Correct 205 ms 18528 KB Output is correct
13 Correct 124 ms 18344 KB Output is correct
14 Correct 167 ms 21424 KB Output is correct
15 Correct 811 ms 53464 KB Output is correct
16 Correct 167 ms 21256 KB Output is correct
17 Correct 846 ms 53340 KB Output is correct
18 Correct 686 ms 52812 KB Output is correct
19 Correct 804 ms 53408 KB Output is correct
20 Correct 776 ms 53308 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12756 KB Output is correct
2 Correct 8 ms 12796 KB Output is correct
3 Correct 164 ms 17740 KB Output is correct
4 Correct 741 ms 55632 KB Output is correct
5 Correct 802 ms 53444 KB Output is correct
6 Correct 847 ms 52956 KB Output is correct
7 Correct 862 ms 53156 KB Output is correct
8 Correct 826 ms 53440 KB Output is correct
9 Correct 785 ms 53320 KB Output is correct
10 Correct 782 ms 52560 KB Output is correct
11 Correct 659 ms 52428 KB Output is correct
12 Correct 768 ms 52684 KB Output is correct
13 Correct 869 ms 52688 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12836 KB Output is correct
2 Correct 9 ms 12840 KB Output is correct
3 Correct 9 ms 12840 KB Output is correct
4 Correct 10 ms 12840 KB Output is correct
5 Correct 10 ms 12808 KB Output is correct
6 Correct 16 ms 12960 KB Output is correct
7 Correct 62 ms 13748 KB Output is correct
8 Correct 34 ms 13772 KB Output is correct
9 Correct 53 ms 13736 KB Output is correct
10 Correct 32 ms 13772 KB Output is correct
11 Correct 61 ms 13736 KB Output is correct
12 Correct 53 ms 13772 KB Output is correct
13 Correct 35 ms 13820 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12848 KB Output is correct
2 Correct 8 ms 12748 KB Output is correct
3 Correct 8 ms 12836 KB Output is correct
4 Correct 8 ms 12756 KB Output is correct
5 Correct 11 ms 13012 KB Output is correct
6 Correct 794 ms 51868 KB Output is correct
7 Correct 907 ms 52180 KB Output is correct
8 Correct 858 ms 52240 KB Output is correct
9 Correct 958 ms 52428 KB Output is correct
10 Correct 786 ms 52468 KB Output is correct
11 Correct 717 ms 52976 KB Output is correct
12 Correct 660 ms 55408 KB Output is correct
13 Correct 769 ms 52764 KB Output is correct
14 Correct 760 ms 52184 KB Output is correct
15 Correct 811 ms 52260 KB Output is correct
16 Correct 638 ms 51752 KB Output is correct
17 Correct 715 ms 51916 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12756 KB Output is correct
2 Correct 8 ms 12756 KB Output is correct
3 Correct 8 ms 12756 KB Output is correct
4 Correct 8 ms 12756 KB Output is correct
5 Correct 8 ms 12832 KB Output is correct
6 Correct 203 ms 16664 KB Output is correct
7 Correct 270 ms 21276 KB Output is correct
8 Correct 620 ms 52724 KB Output is correct
9 Correct 623 ms 52448 KB Output is correct
10 Correct 627 ms 52592 KB Output is correct
11 Correct 653 ms 52536 KB Output is correct
12 Correct 665 ms 52556 KB Output is correct
13 Correct 636 ms 52548 KB Output is correct
14 Correct 700 ms 52656 KB Output is correct
15 Correct 8 ms 12776 KB Output is correct
16 Correct 8 ms 12836 KB Output is correct
17 Correct 9 ms 12796 KB Output is correct
18 Correct 8 ms 12756 KB Output is correct
19 Correct 9 ms 12844 KB Output is correct
20 Correct 13 ms 13056 KB Output is correct
21 Correct 122 ms 18364 KB Output is correct
22 Correct 11 ms 12852 KB Output is correct
23 Correct 13 ms 13108 KB Output is correct
24 Correct 122 ms 18400 KB Output is correct
25 Correct 150 ms 18336 KB Output is correct
26 Correct 205 ms 18528 KB Output is correct
27 Correct 124 ms 18344 KB Output is correct
28 Correct 167 ms 21424 KB Output is correct
29 Correct 811 ms 53464 KB Output is correct
30 Correct 167 ms 21256 KB Output is correct
31 Correct 846 ms 53340 KB Output is correct
32 Correct 686 ms 52812 KB Output is correct
33 Correct 804 ms 53408 KB Output is correct
34 Correct 776 ms 53308 KB Output is correct
35 Correct 8 ms 12756 KB Output is correct
36 Correct 8 ms 12796 KB Output is correct
37 Correct 164 ms 17740 KB Output is correct
38 Correct 741 ms 55632 KB Output is correct
39 Correct 802 ms 53444 KB Output is correct
40 Correct 847 ms 52956 KB Output is correct
41 Correct 862 ms 53156 KB Output is correct
42 Correct 826 ms 53440 KB Output is correct
43 Correct 785 ms 53320 KB Output is correct
44 Correct 782 ms 52560 KB Output is correct
45 Correct 659 ms 52428 KB Output is correct
46 Correct 768 ms 52684 KB Output is correct
47 Correct 869 ms 52688 KB Output is correct
48 Correct 9 ms 12836 KB Output is correct
49 Correct 9 ms 12840 KB Output is correct
50 Correct 9 ms 12840 KB Output is correct
51 Correct 10 ms 12840 KB Output is correct
52 Correct 10 ms 12808 KB Output is correct
53 Correct 16 ms 12960 KB Output is correct
54 Correct 62 ms 13748 KB Output is correct
55 Correct 34 ms 13772 KB Output is correct
56 Correct 53 ms 13736 KB Output is correct
57 Correct 32 ms 13772 KB Output is correct
58 Correct 61 ms 13736 KB Output is correct
59 Correct 53 ms 13772 KB Output is correct
60 Correct 35 ms 13820 KB Output is correct
61 Correct 265 ms 17680 KB Output is correct
62 Correct 308 ms 21240 KB Output is correct
63 Correct 765 ms 52476 KB Output is correct
64 Correct 769 ms 52664 KB Output is correct
65 Correct 887 ms 52944 KB Output is correct
66 Correct 844 ms 53148 KB Output is correct
67 Correct 834 ms 53372 KB Output is correct
68 Correct 746 ms 53712 KB Output is correct
69 Correct 781 ms 53948 KB Output is correct
70 Correct 811 ms 56092 KB Output is correct
71 Correct 876 ms 53508 KB Output is correct
72 Correct 879 ms 53084 KB Output is correct
73 Correct 877 ms 53308 KB Output is correct
74 Correct 756 ms 52608 KB Output is correct
75 Correct 693 ms 52900 KB Output is correct