oj.uz

Submission #415711

# Submission time Handle Problem Language Result Execution time Memory
415711 2021-06-01T11:57:27 Z valerikk Rainforest Jumps (APIO21_jumps) C++17
31 / 100
 4000 ms 48412 KB 
#include <bits/stdc++.h>

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

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

int n, h[N];
int l[N][L], r[N][L];
int big[N][L];

void build() {
    for (int i = 0; i < n; ++i) {
        l[i][0] = -1;
        r[i][0] = -1;
        big[i][0] = -1;
    }
    vector<int> st;
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && h[st.back()] < h[i]) {
            r[st.back()][0] = i;
            st.pop_back();
        }
        st.push_back(i);
    }
    st.clear();
    for (int i = n - 1; i >= 0; --i) {
        while (!st.empty() && h[st.back()] < h[i]) {
            l[st.back()][0] = i;
            st.pop_back();
        }
        st.push_back(i);
    }
    st.clear();
    for (int i = 0; i < n; ++i) {
        if (l[i][0] != -1 && (big[i][0] == -1 || h[l[i][0]] > h[big[i][0]])) big[i][0] = l[i][0];
        if (r[i][0] != -1 && (big[i][0] == -1 || h[r[i][0]] > h[big[i][0]])) big[i][0] = r[i][0];
    }
    for (int p = 1; p < L; ++p) {
        for (int i = 0; i < n; ++i) {
            l[i][p] = l[i][p - 1] == -1 ? -1 : l[l[i][p - 1]][p - 1];
            r[i][p] = r[i][p - 1] == -1 ? -1 : r[r[i][p - 1]][p - 1];
            big[i][p] = big[i][p - 1] == -1 ? -1 : big[big[i][p - 1]][p - 1];
        }
    }
}

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

int get_dist(int s, int t) {
    int res = 0;
    for (int i = L - 1; i >= 0; --i) {
        if (big[s][i] != -1 && h[big[s][i]] <= h[t]) {
            res += (1 << i);
            s = big[s][i];
        }
    }
    for (int i = L - 1; i >= 0; --i) {
        if (r[s][i] != -1 && h[r[s][i]] <= h[t]) {
            res += (1 << i);
            s = r[s][i];
        }
    }
    return s == t ? res : INF;
}

int minimum_jumps(int A, int B, int C, int D) {
    int a = A, b = B, c = C, d = D;
    int res = INF;
    for (int s = a; s <= b; ++s) {
        for (int t = c; t <= d; ++t) res = min(res, get_dist(s, t));
    }
    return res == INF ? -1 : res;
}

#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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Execution timed out 4098 ms 38792 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 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 4 ms 200 KB Output is correct
6 Correct 25 ms 328 KB Output is correct
7 Correct 11 ms 328 KB Output is correct
8 Correct 19 ms 296 KB Output is correct
9 Correct 5 ms 328 KB Output is correct
10 Correct 20 ms 328 KB Output is correct
11 Correct 32 ms 328 KB Output is correct
12 Correct 31 ms 328 KB Output is correct
13 Correct 20 ms 328 KB Output is correct
14 Correct 16 ms 328 KB Output is correct
15 Correct 31 ms 328 KB Output is correct
16 Correct 26 ms 376 KB Output is correct
17 Correct 5 ms 328 KB Output is correct
18 Correct 1 ms 328 KB Output is correct
19 Correct 2 ms 328 KB Output is correct
20 Correct 4 ms 328 KB Output is correct
21 Correct 8 ms 328 KB Output is correct
22 Correct 3 ms 328 KB Output is correct
23 Correct 11 ms 328 KB Output is correct
24 Correct 6 ms 328 KB Output is correct
25 Correct 2 ms 200 KB Output is correct
26 Correct 2 ms 200 KB Output is correct
27 Correct 5 ms 200 KB Output is correct
28 Correct 2 ms 328 KB Output is correct
29 Correct 6 ms 328 KB Output is correct
30 Correct 4 ms 328 KB Output is correct
31 Correct 6 ms 328 KB Output is correct
32 Correct 2 ms 328 KB Output is correct
33 Correct 2 ms 328 KB Output is correct
34 Correct 2 ms 328 KB Output is correct
35 Correct 2 ms 328 KB Output is correct
36 Correct 2 ms 368 KB Output is correct
37 Correct 3 ms 328 KB Output is correct
38 Correct 2 ms 328 KB Output is correct
39 Correct 3 ms 328 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 4 ms 200 KB Output is correct
6 Correct 25 ms 328 KB Output is correct
7 Correct 11 ms 328 KB Output is correct
8 Correct 19 ms 296 KB Output is correct
9 Correct 5 ms 328 KB Output is correct
10 Correct 20 ms 328 KB Output is correct
11 Correct 32 ms 328 KB Output is correct
12 Correct 31 ms 328 KB Output is correct
13 Correct 20 ms 328 KB Output is correct
14 Correct 16 ms 328 KB Output is correct
15 Correct 31 ms 328 KB Output is correct
16 Correct 26 ms 376 KB Output is correct
17 Correct 5 ms 328 KB Output is correct
18 Correct 1 ms 328 KB Output is correct
19 Correct 2 ms 328 KB Output is correct
20 Correct 4 ms 328 KB Output is correct
21 Correct 8 ms 328 KB Output is correct
22 Correct 3 ms 328 KB Output is correct
23 Correct 11 ms 328 KB Output is correct
24 Correct 6 ms 328 KB Output is correct
25 Correct 2 ms 200 KB Output is correct
26 Correct 2 ms 200 KB Output is correct
27 Correct 5 ms 200 KB Output is correct
28 Correct 2 ms 328 KB Output is correct
29 Correct 6 ms 328 KB Output is correct
30 Correct 4 ms 328 KB Output is correct
31 Correct 6 ms 328 KB Output is correct
32 Correct 2 ms 328 KB Output is correct
33 Correct 2 ms 328 KB Output is correct
34 Correct 2 ms 328 KB Output is correct
35 Correct 2 ms 328 KB Output is correct
36 Correct 2 ms 368 KB Output is correct
37 Correct 3 ms 328 KB Output is correct
38 Correct 2 ms 328 KB Output is correct
39 Correct 3 ms 328 KB Output is correct
40 Correct 1 ms 200 KB Output is correct
41 Correct 1 ms 200 KB Output is correct
42 Correct 1 ms 200 KB Output is correct
43 Correct 1 ms 200 KB Output is correct
44 Correct 2 ms 328 KB Output is correct
45 Correct 19 ms 328 KB Output is correct
46 Correct 9 ms 328 KB Output is correct
47 Correct 14 ms 328 KB Output is correct
48 Correct 3 ms 328 KB Output is correct
49 Correct 16 ms 328 KB Output is correct
50 Correct 26 ms 328 KB Output is correct
51 Correct 24 ms 328 KB Output is correct
52 Correct 19 ms 328 KB Output is correct
53 Correct 22 ms 328 KB Output is correct
54 Correct 24 ms 328 KB Output is correct
55 Correct 15 ms 384 KB Output is correct
56 Correct 6 ms 328 KB Output is correct
57 Correct 1 ms 328 KB Output is correct
58 Execution timed out 4026 ms 712 KB Time limit exceeded
59 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Execution timed out 4072 ms 38048 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 463 ms 21784 KB Output is correct
5 Correct 1651 ms 47256 KB Output is correct
6 Correct 730 ms 8008 KB Output is correct
7 Correct 1400 ms 47248 KB Output is correct
8 Correct 981 ms 16444 KB Output is correct
9 Correct 1423 ms 47168 KB Output is correct
10 Correct 1588 ms 48300 KB Output is correct
11 Correct 1674 ms 48360 KB Output is correct
12 Correct 1472 ms 48296 KB Output is correct
13 Correct 1729 ms 47132 KB Output is correct
14 Correct 1208 ms 47788 KB Output is correct
15 Correct 1162 ms 48400 KB Output is correct
16 Correct 1385 ms 48396 KB Output is correct
17 Correct 2 ms 200 KB Output is correct
18 Correct 2 ms 328 KB Output is correct
19 Correct 3 ms 328 KB Output is correct
20 Correct 4 ms 328 KB Output is correct
21 Correct 2 ms 328 KB Output is correct
22 Correct 5 ms 328 KB Output is correct
23 Correct 3 ms 328 KB Output is correct
24 Correct 5 ms 328 KB Output is correct
25 Correct 1 ms 328 KB Output is correct
26 Correct 3 ms 456 KB Output is correct
27 Correct 34 ms 712 KB Output is correct
28 Correct 33 ms 712 KB Output is correct
29 Correct 39 ms 712 KB Output is correct
30 Correct 31 ms 712 KB Output is correct
31 Correct 18 ms 712 KB Output is correct
32 Correct 1 ms 200 KB Output is correct
33 Correct 85 ms 27496 KB Output is correct
34 Correct 171 ms 47280 KB Output is correct
35 Correct 148 ms 48412 KB Output is correct
36 Correct 151 ms 47168 KB Output is correct
37 Correct 179 ms 47788 KB Output is correct
38 Correct 120 ms 48396 KB Output is correct

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 463 ms 21784 KB Output is correct
5 Correct 1651 ms 47256 KB Output is correct
6 Correct 730 ms 8008 KB Output is correct
7 Correct 1400 ms 47248 KB Output is correct
8 Correct 981 ms 16444 KB Output is correct
9 Correct 1423 ms 47168 KB Output is correct
10 Correct 1588 ms 48300 KB Output is correct
11 Correct 1674 ms 48360 KB Output is correct
12 Correct 1472 ms 48296 KB Output is correct
13 Correct 1729 ms 47132 KB Output is correct
14 Correct 1208 ms 47788 KB Output is correct
15 Correct 1162 ms 48400 KB Output is correct
16 Correct 1385 ms 48396 KB Output is correct
17 Correct 2 ms 200 KB Output is correct
18 Correct 2 ms 328 KB Output is correct
19 Correct 3 ms 328 KB Output is correct
20 Correct 4 ms 328 KB Output is correct
21 Correct 2 ms 328 KB Output is correct
22 Correct 5 ms 328 KB Output is correct
23 Correct 3 ms 328 KB Output is correct
24 Correct 5 ms 328 KB Output is correct
25 Correct 1 ms 328 KB Output is correct
26 Correct 3 ms 456 KB Output is correct
27 Correct 34 ms 712 KB Output is correct
28 Correct 33 ms 712 KB Output is correct
29 Correct 39 ms 712 KB Output is correct
30 Correct 31 ms 712 KB Output is correct
31 Correct 18 ms 712 KB Output is correct
32 Correct 1 ms 200 KB Output is correct
33 Correct 85 ms 27496 KB Output is correct
34 Correct 171 ms 47280 KB Output is correct
35 Correct 148 ms 48412 KB Output is correct
36 Correct 151 ms 47168 KB Output is correct
37 Correct 179 ms 47788 KB Output is correct
38 Correct 120 ms 48396 KB Output is correct
39 Correct 1 ms 200 KB Output is correct
40 Correct 1 ms 200 KB Output is correct
41 Correct 2 ms 200 KB Output is correct
42 Correct 373 ms 21776 KB Output is correct
43 Correct 1034 ms 47252 KB Output is correct
44 Correct 666 ms 8024 KB Output is correct
45 Correct 1222 ms 47256 KB Output is correct
46 Correct 680 ms 16456 KB Output is correct
47 Correct 1243 ms 47252 KB Output is correct
48 Correct 1311 ms 48392 KB Output is correct
49 Correct 1391 ms 48288 KB Output is correct
50 Correct 1735 ms 48396 KB Output is correct
51 Correct 1312 ms 47256 KB Output is correct
52 Correct 1393 ms 47876 KB Output is correct
53 Correct 1333 ms 48368 KB Output is correct
54 Correct 1542 ms 48292 KB Output is correct
55 Correct 2 ms 200 KB Output is correct
56 Execution timed out 4062 ms 47076 KB Time limit exceeded
57 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Execution timed out 4098 ms 38792 KB Time limit exceeded
4 Halted 0 ms 0 KB -