oj.uz

Submission #415736

# Submission time Handle Problem Language Result Execution time Memory
415736 2021-06-01T12:25:08 Z valerikk Rainforest Jumps (APIO21_jumps) C++17
48 / 100
 1951 ms 64412 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;

const int N = 2e5 + 7;
const int LG = 19;
const int INF = 1e9;

int n, h[N];
int go_l[N], go_r[N], go_mx[N];
int bin_l[LG][N], bin_r[LG][N], bin_mx[LG][N];
int lg[N];
int sparse[LG][N];

int get_max(int l, int r) {
    if (l >= r) return -INF;
    int t = lg[r - l];
    return max(sparse[t][l], sparse[t][r - (1 << t)]);
}

void build() {
    vector<int> st;
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && h[st.back()] < h[i]) {
            go_r[st.back()] = i;
            st.pop_back();
        }
        st.push_back(i);
    }
    st.clear();
    go_r[n - 1] = n - 1;
    for (int i = n - 1; i >= 0; --i) {
        while (!st.empty() && h[st.back()] < h[i]) {
            go_l[st.back()] = i;
            st.pop_back();
        }
        st.push_back(i);
    }
    st.clear();
    go_l[0] = 0;
    for (int i = 0; i < n; ++i) {
        if (h[go_l[i]] > h[go_r[i]]) go_mx[i] = go_l[i]; else go_mx[i] = go_r[i];
    }
    for (int i = 0; i < n; ++i) {
        bin_l[0][i] = go_l[i];
        bin_r[0][i] = go_r[i];
        bin_mx[0][i] = go_mx[i];
        sparse[0][i] = h[i];
    }
    for (int t = 1; t < LG; ++t) {
        for (int i = 0; i < n; ++i) {
            bin_l[t][i] = bin_l[t - 1][bin_l[t - 1][i]];
            bin_r[t][i] = bin_r[t - 1][bin_r[t - 1][i]];
            bin_mx[t][i] = bin_mx[t - 1][bin_mx[t - 1][i]];
            if (i + (1 << t) <= n) sparse[t][i] = max(sparse[t - 1][i], sparse[t - 1][i + (1 << (t - 1))]);
        }
    }
    lg[0] = lg[1] = 0;
    for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
}

void init(int n2, vector<int> h2) {
    for (int i = 1; i <= n2; ++i) h[i] = h2[i - 1] - 1;
    h[0] = n2;
    h[n2 + 1] = n2 + 1;
    n = n2 + 2;
    build();
}

int minimum_jumps(int A, int B, int C, int D) {
    int a = A + 1, b = B + 2, c = C + 1, d = D + 2;
    int mx = get_max(c, d);
    int v = b - 1;
    for (int i = LG - 1; i >= 0; --i) {
        if (bin_l[i][v] >= a && h[bin_l[i][v]] < mx) v = bin_l[i][v];
    }
    int mx2 = get_max(b, c);
    int res = 0;
    for (int i = LG - 1; i >= 0; --i) {
        if (h[bin_mx[i][v]] < mx2) {
            res += (1 << i);
            v = bin_mx[i][v];
        }
    }
    if (h[go_mx[v]] >= mx2 && h[go_mx[v]] <= mx) {
        ++res;
        v = go_mx[v];
    }
    for (int i = LG - 1; i >= 0; --i) {
        if (bin_r[i][v] < c) {
            v = bin_r[i][v];
            res += (1 << i);
        }
    }
    if (v >= c && v < d) return res;
    if (go_r[v] >= c && go_r[v] < d) return res + 1;
    return -1;
}

#ifdef LOCAL
int main() {
    freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n2, q2;
    cin >> n2 >> q2;
    vector<int> h2(n2);
    for (auto &i : h2) cin >> i;
    init(n2, h2);
    while (q2--) {
        int A, B, C, D;
        cin >> A >> B >> C >> D;
        cout << minimum_jumps(A, B, C, D) << endl;
    }
    return 0;
}
#endif

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 584 KB Output is correct
2 Correct 2 ms 584 KB Output is correct
3 Correct 161 ms 51348 KB Output is correct
4 Correct 1616 ms 64288 KB Output is correct
5 Correct 1174 ms 32520 KB Output is correct
6 Correct 1951 ms 64348 KB Output is correct
7 Correct 1425 ms 44032 KB Output is correct
8 Correct 1420 ms 64292 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 584 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 1 ms 584 KB Output is correct
4 Correct 1 ms 584 KB Output is correct
5 Correct 75 ms 51136 KB Output is correct
6 Correct 87 ms 63476 KB Output is correct
7 Correct 38 ms 32568 KB Output is correct
8 Correct 92 ms 63404 KB Output is correct
9 Correct 15 ms 9764 KB Output is correct
10 Correct 88 ms 63384 KB Output is correct
11 Correct 84 ms 64308 KB Output is correct
12 Correct 70 ms 64180 KB Output is correct
13 Correct 78 ms 64056 KB Output is correct
14 Correct 74 ms 63388 KB Output is correct
15 Correct 90 ms 64008 KB Output is correct
16 Correct 86 ms 64280 KB Output is correct
17 Correct 80 ms 64268 KB Output is correct
18 Correct 1 ms 584 KB Output is correct
19 Correct 2 ms 712 KB Output is correct
20 Correct 1 ms 712 KB Output is correct
21 Correct 2 ms 712 KB Output is correct
22 Incorrect 1 ms 712 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 584 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 2 ms 584 KB Output is correct
4 Correct 392 ms 29040 KB Output is correct
5 Correct 1556 ms 63376 KB Output is correct
6 Correct 890 ms 10700 KB Output is correct
7 Correct 1411 ms 63388 KB Output is correct
8 Correct 879 ms 21960 KB Output is correct
9 Correct 1194 ms 63396 KB Output is correct
10 Correct 1711 ms 64400 KB Output is correct
11 Correct 1535 ms 64288 KB Output is correct
12 Correct 1390 ms 64268 KB Output is correct
13 Correct 1336 ms 63424 KB Output is correct
14 Correct 1439 ms 63936 KB Output is correct
15 Correct 1435 ms 64324 KB Output is correct
16 Correct 1261 ms 64288 KB Output is correct
17 Correct 1 ms 584 KB Output is correct
18 Correct 1 ms 584 KB Output is correct
19 Correct 4 ms 584 KB Output is correct
20 Correct 5 ms 712 KB Output is correct
21 Correct 5 ms 712 KB Output is correct
22 Correct 4 ms 712 KB Output is correct
23 Correct 4 ms 712 KB Output is correct
24 Correct 8 ms 712 KB Output is correct
25 Correct 1 ms 712 KB Output is correct
26 Correct 4 ms 840 KB Output is correct
27 Correct 28 ms 1224 KB Output is correct
28 Correct 26 ms 1284 KB Output is correct
29 Correct 19 ms 1224 KB Output is correct
30 Correct 22 ms 1224 KB Output is correct
31 Correct 47 ms 1224 KB Output is correct
32 Correct 1 ms 584 KB Output is correct
33 Correct 50 ms 36832 KB Output is correct
34 Correct 72 ms 63404 KB Output is correct
35 Correct 84 ms 64248 KB Output is correct
36 Correct 91 ms 63424 KB Output is correct
37 Correct 71 ms 63928 KB Output is correct
38 Correct 73 ms 64376 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 584 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 2 ms 584 KB Output is correct
4 Correct 392 ms 29040 KB Output is correct
5 Correct 1556 ms 63376 KB Output is correct
6 Correct 890 ms 10700 KB Output is correct
7 Correct 1411 ms 63388 KB Output is correct
8 Correct 879 ms 21960 KB Output is correct
9 Correct 1194 ms 63396 KB Output is correct
10 Correct 1711 ms 64400 KB Output is correct
11 Correct 1535 ms 64288 KB Output is correct
12 Correct 1390 ms 64268 KB Output is correct
13 Correct 1336 ms 63424 KB Output is correct
14 Correct 1439 ms 63936 KB Output is correct
15 Correct 1435 ms 64324 KB Output is correct
16 Correct 1261 ms 64288 KB Output is correct
17 Correct 1 ms 584 KB Output is correct
18 Correct 1 ms 584 KB Output is correct
19 Correct 4 ms 584 KB Output is correct
20 Correct 5 ms 712 KB Output is correct
21 Correct 5 ms 712 KB Output is correct
22 Correct 4 ms 712 KB Output is correct
23 Correct 4 ms 712 KB Output is correct
24 Correct 8 ms 712 KB Output is correct
25 Correct 1 ms 712 KB Output is correct
26 Correct 4 ms 840 KB Output is correct
27 Correct 28 ms 1224 KB Output is correct
28 Correct 26 ms 1284 KB Output is correct
29 Correct 19 ms 1224 KB Output is correct
30 Correct 22 ms 1224 KB Output is correct
31 Correct 47 ms 1224 KB Output is correct
32 Correct 1 ms 584 KB Output is correct
33 Correct 50 ms 36832 KB Output is correct
34 Correct 72 ms 63404 KB Output is correct
35 Correct 84 ms 64248 KB Output is correct
36 Correct 91 ms 63424 KB Output is correct
37 Correct 71 ms 63928 KB Output is correct
38 Correct 73 ms 64376 KB Output is correct
39 Correct 1 ms 584 KB Output is correct
40 Correct 1 ms 584 KB Output is correct
41 Correct 1 ms 584 KB Output is correct
42 Correct 319 ms 29040 KB Output is correct
43 Correct 1147 ms 63424 KB Output is correct
44 Correct 1052 ms 10684 KB Output is correct
45 Correct 1402 ms 63424 KB Output is correct
46 Correct 611 ms 21912 KB Output is correct
47 Correct 1452 ms 63388 KB Output is correct
48 Correct 1176 ms 64412 KB Output is correct
49 Correct 1417 ms 64316 KB Output is correct
50 Correct 1422 ms 64272 KB Output is correct
51 Correct 1091 ms 63424 KB Output is correct
52 Correct 1469 ms 63888 KB Output is correct
53 Correct 1320 ms 64348 KB Output is correct
54 Correct 1217 ms 64308 KB Output is correct
55 Correct 1 ms 584 KB Output is correct
56 Correct 167 ms 63424 KB Output is correct
57 Correct 1660 ms 63404 KB Output is correct
58 Correct 870 ms 11396 KB Output is correct
59 Correct 1605 ms 63404 KB Output is correct
60 Correct 538 ms 22556 KB Output is correct
61 Correct 1693 ms 63400 KB Output is correct
62 Correct 1460 ms 64268 KB Output is correct
63 Correct 1246 ms 64144 KB Output is correct
64 Correct 1596 ms 64056 KB Output is correct
65 Correct 1408 ms 63408 KB Output is correct
66 Correct 1914 ms 63924 KB Output is correct
67 Correct 1659 ms 64376 KB Output is correct
68 Correct 1667 ms 64308 KB Output is correct
69 Correct 1 ms 584 KB Output is correct
70 Correct 3 ms 584 KB Output is correct
71 Correct 6 ms 712 KB Output is correct
72 Correct 3 ms 712 KB Output is correct
73 Correct 6 ms 712 KB Output is correct
74 Correct 3 ms 712 KB Output is correct
75 Correct 4 ms 712 KB Output is correct
76 Correct 1 ms 584 KB Output is correct
77 Correct 1 ms 584 KB Output is correct
78 Correct 3 ms 584 KB Output is correct
79 Correct 3 ms 712 KB Output is correct
80 Correct 4 ms 712 KB Output is correct
81 Correct 5 ms 712 KB Output is correct
82 Correct 3 ms 712 KB Output is correct
83 Correct 4 ms 712 KB Output is correct
84 Correct 1 ms 712 KB Output is correct
85 Correct 7 ms 712 KB Output is correct
86 Correct 23 ms 1224 KB Output is correct
87 Correct 33 ms 1224 KB Output is correct
88 Correct 19 ms 1224 KB Output is correct
89 Correct 14 ms 1340 KB Output is correct
90 Correct 18 ms 1224 KB Output is correct
91 Correct 1 ms 712 KB Output is correct
92 Correct 2 ms 840 KB Output is correct
93 Correct 24 ms 1180 KB Output is correct
94 Correct 23 ms 1224 KB Output is correct
95 Correct 32 ms 1224 KB Output is correct
96 Correct 19 ms 1224 KB Output is correct
97 Correct 31 ms 1188 KB Output is correct
98 Correct 1 ms 584 KB Output is correct
99 Correct 79 ms 63376 KB Output is correct
100 Correct 104 ms 63424 KB Output is correct
101 Correct 88 ms 64184 KB Output is correct
102 Correct 78 ms 63372 KB Output is correct
103 Correct 70 ms 63876 KB Output is correct
104 Correct 97 ms 64400 KB Output is correct
105 Correct 1 ms 584 KB Output is correct
106 Correct 50 ms 36764 KB Output is correct
107 Correct 80 ms 63376 KB Output is correct
108 Correct 71 ms 64160 KB Output is correct
109 Correct 96 ms 63376 KB Output is correct
110 Correct 73 ms 63888 KB Output is correct
111 Correct 92 ms 64404 KB Output is correct

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 584 KB Output is correct
2 Correct 2 ms 584 KB Output is correct
3 Correct 161 ms 51348 KB Output is correct
4 Correct 1616 ms 64288 KB Output is correct
5 Correct 1174 ms 32520 KB Output is correct
6 Correct 1951 ms 64348 KB Output is correct
7 Correct 1425 ms 44032 KB Output is correct
8 Correct 1420 ms 64292 KB Output is correct
9 Correct 1 ms 584 KB Output is correct
10 Correct 1 ms 584 KB Output is correct
11 Correct 1 ms 584 KB Output is correct
12 Correct 1 ms 584 KB Output is correct
13 Correct 2 ms 584 KB Output is correct
14 Incorrect 4 ms 712 KB Output isn't correct
15 Halted 0 ms 0 KB -