oj.uz

Submission #971464

# Submission time Handle Problem Language Result Execution time Memory
971464 2024-04-28T14:52:20 Z Pannda Rainforest Jumps (APIO21_jumps) C++17
77 / 100
 4000 ms 32856 KB 
#include "jumps.h"

#include <bits/stdc++.h>
using namespace std;

struct SegmentTree {
    int n;
    vector<int> mx;
    vector<int> mn;

    SegmentTree() {}
    SegmentTree(vector<int> a) : n(a.size()), mx(4 * n), mn(4 * n) {
        auto dfs = [&](auto self, int idx, int l, int r) -> void {
            if (l + 1 == r) {
                mn[idx] = mx[idx] = a[l];
            } else {
                int m = (l + r) >> 1;
                self(self, 2 * idx + 1, l, m);
                self(self, 2 * idx + 2, m, r);
                mn[idx] = min(mn[2 * idx + 1], mn[2 * idx + 2]);
                mx[idx] = max(mx[2 * idx + 1], mx[2 * idx + 2]);
            }
        };
        dfs(dfs, 0, 0, n);
    }

    int find(int ql, int qr, int ub, int rb) {
        auto walk = [&](auto self, int idx, int l, int r) -> int {
            if (rb <= l) return -1;
            if (mx[idx] < ub) return -1;
            if (l + 1 == r) {
                return l;
            }
            int m = (l + r) >> 1;
            int get = self(self, 2 * idx + 2, m, r);
            if (get != -1) return get;
            return self(self, 2 * idx + 1, l, m);
        };
        int get = walk(walk, 0, 0, n);
        ql = max(ql, get + 1);
        if (ql >= qr) return -1;
        auto dfs = [&](auto self, int idx, int l, int r) -> int {
            if (r <= ql || qr <= l) return -1;
            if (ql <= l && r <= qr) return mx[idx];
            int m = (l + r) >> 1;
            return max(self(self, 2 * idx + 1, l, m), self(self, 2 * idx + 2, m, r));
        };
        return dfs(dfs, 0, 0, n);
    }

};

const int LOG = 17;
int n;
vector<int> h, ih;
SegmentTree seg;
vector<vector<int>> f;
vector<int> depth;

void init(int N, vector<int> H) {
    n = N;
    h = H;
    ih = vector<int>(n);
    for (int i = 0; i < n; i++) {
        h[i]--;
        ih[h[i]] = i;
    }
    seg = SegmentTree(h);
    h.push_back(n);
    f = vector<vector<int>>(n + 1, vector<int>(LOG, n));
    depth = vector<int>(n + 1, 0);

    vector<int> stk = { n };
    for (int i = n - 1; i >= 0; i--) {
        while (h[stk.back()] < h[i]) stk.pop_back();
        depth[i] = depth[stk.back()] + 1;
        f[i][0] = stk.back();
        stk.push_back(i);
    }

    stk.clear();
    for (int i = 0; i < n; i++) {
        while (!stk.empty() && h[stk.back()] < h[i]) stk.pop_back();
        if (!stk.empty() && depth[stk.back()] <= depth[f[i][0]]) {
            f[i][0] = stk.back();
        }
        stk.push_back(i);
    }

    for (int k = 1; k < LOG; k++) {
        for (int i = 0; i < n; i++) {
            f[i][k] = f[f[i][k - 1]][k - 1];
        }
    }
}

int minimum_jumps(int l0, int r0, int l1, int r1) {
    r0++; r1++;
    int res = n;
    for (int to = l1; to < r1; to++) {
        int from = seg.find(l0, r0, h[to], to);
        if (from == -1) continue;
        from = ih[from];
        int cnt = 0;
        for (int k = LOG - 1; k >= 0; k--) {
            int next = f[from][k];
            if (depth[next] >= depth[to] && h[next] < h[to]) {
                from = next;
                cnt += 1 << k;
            }
        }
        res = min(res, cnt + depth[from] - depth[to]);
    }
    if (res == n) return -1;
    return res;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Execution timed out 4032 ms 26248 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 2 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 2 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 2 ms 344 KB Output is correct
12 Correct 2 ms 344 KB Output is correct
13 Correct 2 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 2 ms 344 KB Output is correct
16 Correct 2 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 596 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 1 ms 352 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 0 ms 352 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Correct 1 ms 344 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 344 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 1 ms 344 KB Output is correct
33 Correct 0 ms 344 KB Output is correct
34 Correct 0 ms 344 KB Output is correct
35 Correct 0 ms 344 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 1 ms 344 KB Output is correct
38 Correct 1 ms 344 KB Output is correct
39 Correct 0 ms 344 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 2 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 2 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 2 ms 344 KB Output is correct
12 Correct 2 ms 344 KB Output is correct
13 Correct 2 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 2 ms 344 KB Output is correct
16 Correct 2 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 596 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 1 ms 352 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 0 ms 352 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Correct 1 ms 344 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 344 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 1 ms 344 KB Output is correct
33 Correct 0 ms 344 KB Output is correct
34 Correct 0 ms 344 KB Output is correct
35 Correct 0 ms 344 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 1 ms 344 KB Output is correct
38 Correct 1 ms 344 KB Output is correct
39 Correct 0 ms 344 KB Output is correct
40 Correct 1 ms 344 KB Output is correct
41 Correct 1 ms 344 KB Output is correct
42 Correct 0 ms 344 KB Output is correct
43 Correct 0 ms 344 KB Output is correct
44 Correct 1 ms 344 KB Output is correct
45 Correct 1 ms 344 KB Output is correct
46 Correct 1 ms 344 KB Output is correct
47 Correct 2 ms 344 KB Output is correct
48 Correct 1 ms 344 KB Output is correct
49 Correct 1 ms 344 KB Output is correct
50 Correct 2 ms 344 KB Output is correct
51 Correct 2 ms 344 KB Output is correct
52 Correct 2 ms 344 KB Output is correct
53 Correct 2 ms 344 KB Output is correct
54 Correct 2 ms 344 KB Output is correct
55 Correct 2 ms 344 KB Output is correct
56 Correct 1 ms 344 KB Output is correct
57 Correct 0 ms 344 KB Output is correct
58 Correct 27 ms 600 KB Output is correct
59 Correct 45 ms 600 KB Output is correct
60 Correct 5 ms 344 KB Output is correct
61 Correct 41 ms 600 KB Output is correct
62 Correct 7 ms 344 KB Output is correct
63 Correct 43 ms 600 KB Output is correct
64 Correct 113 ms 600 KB Output is correct
65 Correct 116 ms 600 KB Output is correct
66 Correct 98 ms 600 KB Output is correct
67 Correct 41 ms 600 KB Output is correct
68 Correct 104 ms 600 KB Output is correct
69 Correct 35 ms 600 KB Output is correct
70 Correct 161 ms 852 KB Output is correct
71 Correct 0 ms 344 KB Output is correct
72 Correct 0 ms 344 KB Output is correct
73 Correct 1 ms 344 KB Output is correct
74 Correct 1 ms 344 KB Output is correct
75 Correct 1 ms 344 KB Output is correct
76 Correct 1 ms 344 KB Output is correct
77 Correct 2 ms 344 KB Output is correct
78 Correct 0 ms 344 KB Output is correct
79 Correct 0 ms 344 KB Output is correct
80 Correct 1 ms 344 KB Output is correct
81 Correct 2 ms 344 KB Output is correct
82 Correct 1 ms 344 KB Output is correct
83 Correct 1 ms 344 KB Output is correct
84 Correct 1 ms 344 KB Output is correct
85 Correct 1 ms 344 KB Output is correct
86 Correct 0 ms 344 KB Output is correct
87 Correct 0 ms 344 KB Output is correct
88 Correct 0 ms 344 KB Output is correct
89 Correct 1 ms 596 KB Output is correct
90 Correct 1 ms 344 KB Output is correct
91 Correct 0 ms 344 KB Output is correct
92 Correct 0 ms 344 KB Output is correct
93 Correct 0 ms 344 KB Output is correct
94 Correct 1 ms 344 KB Output is correct
95 Correct 9 ms 600 KB Output is correct
96 Correct 11 ms 600 KB Output is correct
97 Correct 8 ms 600 KB Output is correct
98 Correct 14 ms 600 KB Output is correct
99 Correct 10 ms 600 KB Output is correct
100 Correct 0 ms 344 KB Output is correct
101 Correct 1 ms 344 KB Output is correct
102 Correct 9 ms 600 KB Output is correct
103 Correct 12 ms 600 KB Output is correct
104 Correct 16 ms 600 KB Output is correct
105 Correct 10 ms 600 KB Output is correct
106 Correct 9 ms 600 KB Output is correct
107 Correct 0 ms 344 KB Output is correct
108 Correct 1 ms 344 KB Output is correct
109 Correct 1 ms 600 KB Output is correct
110 Correct 1 ms 600 KB Output is correct
111 Correct 1 ms 600 KB Output is correct
112 Correct 1 ms 600 KB Output is correct
113 Correct 1 ms 600 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 47 ms 24884 KB Output is correct
6 Correct 74 ms 30824 KB Output is correct
7 Correct 25 ms 15916 KB Output is correct
8 Correct 68 ms 30876 KB Output is correct
9 Correct 8 ms 4952 KB Output is correct
10 Correct 77 ms 30972 KB Output is correct
11 Correct 86 ms 32856 KB Output is correct
12 Correct 114 ms 32568 KB Output is correct
13 Correct 69 ms 32704 KB Output is correct
14 Correct 75 ms 30876 KB Output is correct
15 Correct 82 ms 31644 KB Output is correct
16 Correct 68 ms 32680 KB Output is correct
17 Correct 81 ms 32660 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 1 ms 600 KB Output is correct
28 Correct 1 ms 600 KB Output is correct
29 Correct 1 ms 600 KB Output is correct
30 Correct 1 ms 600 KB Output is correct
31 Correct 2 ms 600 KB Output is correct
32 Correct 1 ms 344 KB Output is correct
33 Correct 61 ms 30824 KB Output is correct
34 Correct 59 ms 30752 KB Output is correct
35 Correct 61 ms 32412 KB Output is correct
36 Correct 58 ms 30864 KB Output is correct
37 Correct 65 ms 31888 KB Output is correct
38 Correct 70 ms 32764 KB Output is correct
39 Correct 0 ms 344 KB Output is correct
40 Correct 32 ms 18120 KB Output is correct
41 Correct 59 ms 30848 KB Output is correct
42 Correct 56 ms 32680 KB Output is correct
43 Correct 71 ms 30856 KB Output is correct
44 Correct 60 ms 31652 KB Output is correct
45 Correct 57 ms 32564 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 171 ms 14408 KB Output is correct
5 Correct 634 ms 30880 KB Output is correct
6 Correct 456 ms 5456 KB Output is correct
7 Correct 622 ms 30904 KB Output is correct
8 Correct 379 ms 10916 KB Output is correct
9 Correct 681 ms 30872 KB Output is correct
10 Correct 883 ms 32672 KB Output is correct
11 Correct 714 ms 32656 KB Output is correct
12 Correct 908 ms 32680 KB Output is correct
13 Correct 659 ms 30976 KB Output is correct
14 Correct 851 ms 31636 KB Output is correct
15 Correct 655 ms 32684 KB Output is correct
16 Correct 647 ms 32656 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 13 ms 600 KB Output is correct
28 Correct 10 ms 600 KB Output is correct
29 Correct 12 ms 600 KB Output is correct
30 Correct 13 ms 600 KB Output is correct
31 Correct 13 ms 600 KB Output is correct
32 Correct 0 ms 344 KB Output is correct
33 Correct 30 ms 17908 KB Output is correct
34 Correct 66 ms 30956 KB Output is correct
35 Correct 64 ms 32680 KB Output is correct
36 Correct 68 ms 30888 KB Output is correct
37 Correct 61 ms 31644 KB Output is correct
38 Correct 56 ms 32656 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 171 ms 14408 KB Output is correct
5 Correct 634 ms 30880 KB Output is correct
6 Correct 456 ms 5456 KB Output is correct
7 Correct 622 ms 30904 KB Output is correct
8 Correct 379 ms 10916 KB Output is correct
9 Correct 681 ms 30872 KB Output is correct
10 Correct 883 ms 32672 KB Output is correct
11 Correct 714 ms 32656 KB Output is correct
12 Correct 908 ms 32680 KB Output is correct
13 Correct 659 ms 30976 KB Output is correct
14 Correct 851 ms 31636 KB Output is correct
15 Correct 655 ms 32684 KB Output is correct
16 Correct 647 ms 32656 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 13 ms 600 KB Output is correct
28 Correct 10 ms 600 KB Output is correct
29 Correct 12 ms 600 KB Output is correct
30 Correct 13 ms 600 KB Output is correct
31 Correct 13 ms 600 KB Output is correct
32 Correct 0 ms 344 KB Output is correct
33 Correct 30 ms 17908 KB Output is correct
34 Correct 66 ms 30956 KB Output is correct
35 Correct 64 ms 32680 KB Output is correct
36 Correct 68 ms 30888 KB Output is correct
37 Correct 61 ms 31644 KB Output is correct
38 Correct 56 ms 32656 KB Output is correct
39 Correct 0 ms 344 KB Output is correct
40 Correct 0 ms 344 KB Output is correct
41 Correct 0 ms 344 KB Output is correct
42 Correct 180 ms 14508 KB Output is correct
43 Correct 649 ms 30972 KB Output is correct
44 Correct 415 ms 5456 KB Output is correct
45 Correct 627 ms 31016 KB Output is correct
46 Correct 364 ms 11060 KB Output is correct
47 Correct 629 ms 30884 KB Output is correct
48 Correct 944 ms 32776 KB Output is correct
49 Correct 755 ms 32676 KB Output is correct
50 Correct 873 ms 32668 KB Output is correct
51 Correct 680 ms 31024 KB Output is correct
52 Correct 823 ms 31640 KB Output is correct
53 Correct 647 ms 32656 KB Output is correct
54 Correct 613 ms 32724 KB Output is correct
55 Correct 0 ms 344 KB Output is correct
56 Correct 91 ms 30616 KB Output is correct
57 Correct 591 ms 30968 KB Output is correct
58 Correct 304 ms 5668 KB Output is correct
59 Correct 646 ms 30924 KB Output is correct
60 Correct 252 ms 11168 KB Output is correct
61 Correct 632 ms 30976 KB Output is correct
62 Correct 941 ms 32656 KB Output is correct
63 Correct 753 ms 32404 KB Output is correct
64 Correct 744 ms 31888 KB Output is correct
65 Correct 677 ms 30816 KB Output is correct
66 Correct 810 ms 31876 KB Output is correct
67 Correct 651 ms 32696 KB Output is correct
68 Correct 685 ms 32652 KB Output is correct
69 Correct 0 ms 344 KB Output is correct
70 Correct 0 ms 344 KB Output is correct
71 Correct 1 ms 344 KB Output is correct
72 Correct 1 ms 344 KB Output is correct
73 Correct 1 ms 344 KB Output is correct
74 Correct 1 ms 344 KB Output is correct
75 Correct 1 ms 344 KB Output is correct
76 Correct 0 ms 344 KB Output is correct
77 Correct 0 ms 344 KB Output is correct
78 Correct 1 ms 344 KB Output is correct
79 Correct 1 ms 344 KB Output is correct
80 Correct 1 ms 344 KB Output is correct
81 Correct 1 ms 344 KB Output is correct
82 Correct 1 ms 344 KB Output is correct
83 Correct 1 ms 344 KB Output is correct
84 Correct 0 ms 344 KB Output is correct
85 Correct 2 ms 344 KB Output is correct
86 Correct 9 ms 600 KB Output is correct
87 Correct 10 ms 600 KB Output is correct
88 Correct 11 ms 852 KB Output is correct
89 Correct 10 ms 600 KB Output is correct
90 Correct 8 ms 600 KB Output is correct
91 Correct 0 ms 344 KB Output is correct
92 Correct 1 ms 344 KB Output is correct
93 Correct 9 ms 600 KB Output is correct
94 Correct 9 ms 600 KB Output is correct
95 Correct 11 ms 600 KB Output is correct
96 Correct 9 ms 600 KB Output is correct
97 Correct 11 ms 600 KB Output is correct
98 Correct 0 ms 344 KB Output is correct
99 Correct 62 ms 30668 KB Output is correct
100 Correct 58 ms 30884 KB Output is correct
101 Correct 58 ms 32428 KB Output is correct
102 Correct 59 ms 30880 KB Output is correct
103 Correct 60 ms 31780 KB Output is correct
104 Correct 61 ms 32800 KB Output is correct
105 Correct 0 ms 344 KB Output is correct
106 Correct 34 ms 17904 KB Output is correct
107 Correct 60 ms 30988 KB Output is correct
108 Correct 57 ms 32600 KB Output is correct
109 Correct 64 ms 30876 KB Output is correct
110 Correct 59 ms 31652 KB Output is correct
111 Correct 56 ms 32656 KB Output is correct

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Execution timed out 4032 ms 26248 KB Time limit exceeded
4 Halted 0 ms 0 KB -