oj.uz

Submission #415724

# Submission time Handle Problem Language Result Execution time Memory
415724 2021-06-01T12:12:28 Z valerikk Rainforest Jumps (APIO21_jumps) C++17
31 / 100
 4000 ms 64400 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) {
    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 get_dist(int v, int t) {
    int d = 0;
    for (int i = LG - 1; i >= 0; --i) {
        if (h[bin_mx[i][v]] <= h[t]) {
            d += (1 << i);
            v = bin_mx[i][v];
        }
    }
    for (int i = LG - 1; i >= 0; --i) {
        if (h[bin_r[i][v]] <= h[t]) {
            d += (1 << i);
            v = bin_r[i][v];
        }
    }
    return v == t ? d : INF;
}

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 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 584 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Execution timed out 4054 ms 51460 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

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

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 2 ms 584 KB Output is correct
5 Correct 3 ms 584 KB Output is correct
6 Correct 22 ms 712 KB Output is correct
7 Correct 14 ms 712 KB Output is correct
8 Correct 17 ms 712 KB Output is correct
9 Correct 4 ms 712 KB Output is correct
10 Correct 21 ms 712 KB Output is correct
11 Correct 23 ms 712 KB Output is correct
12 Correct 18 ms 692 KB Output is correct
13 Correct 17 ms 712 KB Output is correct
14 Correct 22 ms 712 KB Output is correct
15 Correct 23 ms 712 KB Output is correct
16 Correct 14 ms 712 KB Output is correct
17 Correct 5 ms 712 KB Output is correct
18 Correct 1 ms 584 KB Output is correct
19 Correct 2 ms 584 KB Output is correct
20 Correct 7 ms 712 KB Output is correct
21 Correct 4 ms 712 KB Output is correct
22 Correct 4 ms 712 KB Output is correct
23 Correct 7 ms 712 KB Output is correct
24 Correct 4 ms 712 KB Output is correct
25 Correct 1 ms 584 KB Output is correct
26 Correct 1 ms 584 KB Output is correct
27 Correct 2 ms 584 KB Output is correct
28 Correct 5 ms 712 KB Output is correct
29 Correct 5 ms 712 KB Output is correct
30 Correct 5 ms 712 KB Output is correct
31 Correct 3 ms 712 KB Output is correct
32 Correct 3 ms 712 KB Output is correct
33 Correct 1 ms 584 KB Output is correct
34 Correct 2 ms 712 KB Output is correct
35 Correct 2 ms 712 KB Output is correct
36 Correct 1 ms 712 KB Output is correct
37 Correct 2 ms 712 KB Output is correct
38 Correct 2 ms 712 KB Output is correct
39 Correct 2 ms 712 KB Output is correct
40 Correct 1 ms 584 KB Output is correct
41 Correct 1 ms 584 KB Output is correct
42 Correct 1 ms 584 KB Output is correct
43 Correct 1 ms 584 KB Output is correct
44 Correct 3 ms 584 KB Output is correct
45 Correct 16 ms 712 KB Output is correct
46 Correct 10 ms 712 KB Output is correct
47 Correct 16 ms 712 KB Output is correct
48 Correct 6 ms 712 KB Output is correct
49 Correct 21 ms 712 KB Output is correct
50 Correct 21 ms 712 KB Output is correct
51 Correct 19 ms 712 KB Output is correct
52 Correct 18 ms 712 KB Output is correct
53 Correct 18 ms 712 KB Output is correct
54 Correct 20 ms 712 KB Output is correct
55 Correct 17 ms 712 KB Output is correct
56 Correct 8 ms 712 KB Output is correct
57 Correct 1 ms 712 KB Output is correct
58 Execution timed out 4083 ms 1096 KB Time limit exceeded
59 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 Execution timed out 4030 ms 51136 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 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 362 ms 29120 KB Output is correct
5 Correct 1195 ms 63428 KB Output is correct
6 Correct 838 ms 10696 KB Output is correct
7 Correct 1090 ms 63388 KB Output is correct
8 Correct 771 ms 21952 KB Output is correct
9 Correct 1254 ms 63408 KB Output is correct
10 Correct 1324 ms 64384 KB Output is correct
11 Correct 1401 ms 64284 KB Output is correct
12 Correct 1454 ms 64272 KB Output is correct
13 Correct 1135 ms 63388 KB Output is correct
14 Correct 1210 ms 63920 KB Output is correct
15 Correct 994 ms 64400 KB Output is correct
16 Correct 962 ms 64372 KB Output is correct
17 Correct 1 ms 584 KB Output is correct
18 Correct 2 ms 584 KB Output is correct
19 Correct 3 ms 584 KB Output is correct
20 Correct 4 ms 712 KB Output is correct
21 Correct 2 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 3 ms 712 KB Output is correct
25 Correct 1 ms 712 KB Output is correct
26 Correct 3 ms 840 KB Output is correct
27 Correct 29 ms 1224 KB Output is correct
28 Correct 27 ms 1224 KB Output is correct
29 Correct 22 ms 1224 KB Output is correct
30 Correct 20 ms 1224 KB Output is correct
31 Correct 22 ms 1224 KB Output is correct
32 Correct 1 ms 584 KB Output is correct
33 Correct 44 ms 36764 KB Output is correct
34 Correct 82 ms 63500 KB Output is correct
35 Correct 72 ms 64180 KB Output is correct
36 Correct 76 ms 63512 KB Output is correct
37 Correct 79 ms 63964 KB Output is correct
38 Correct 72 ms 64372 KB Output is correct

Subtask #6
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 1 ms 584 KB Output is correct
4 Correct 362 ms 29120 KB Output is correct
5 Correct 1195 ms 63428 KB Output is correct
6 Correct 838 ms 10696 KB Output is correct
7 Correct 1090 ms 63388 KB Output is correct
8 Correct 771 ms 21952 KB Output is correct
9 Correct 1254 ms 63408 KB Output is correct
10 Correct 1324 ms 64384 KB Output is correct
11 Correct 1401 ms 64284 KB Output is correct
12 Correct 1454 ms 64272 KB Output is correct
13 Correct 1135 ms 63388 KB Output is correct
14 Correct 1210 ms 63920 KB Output is correct
15 Correct 994 ms 64400 KB Output is correct
16 Correct 962 ms 64372 KB Output is correct
17 Correct 1 ms 584 KB Output is correct
18 Correct 2 ms 584 KB Output is correct
19 Correct 3 ms 584 KB Output is correct
20 Correct 4 ms 712 KB Output is correct
21 Correct 2 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 3 ms 712 KB Output is correct
25 Correct 1 ms 712 KB Output is correct
26 Correct 3 ms 840 KB Output is correct
27 Correct 29 ms 1224 KB Output is correct
28 Correct 27 ms 1224 KB Output is correct
29 Correct 22 ms 1224 KB Output is correct
30 Correct 20 ms 1224 KB Output is correct
31 Correct 22 ms 1224 KB Output is correct
32 Correct 1 ms 584 KB Output is correct
33 Correct 44 ms 36764 KB Output is correct
34 Correct 82 ms 63500 KB Output is correct
35 Correct 72 ms 64180 KB Output is correct
36 Correct 76 ms 63512 KB Output is correct
37 Correct 79 ms 63964 KB Output is correct
38 Correct 72 ms 64372 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 289 ms 29080 KB Output is correct
43 Correct 1224 ms 63424 KB Output is correct
44 Correct 585 ms 10680 KB Output is correct
45 Correct 1362 ms 63424 KB Output is correct
46 Correct 601 ms 21880 KB Output is correct
47 Correct 1110 ms 63424 KB Output is correct
48 Correct 1232 ms 64296 KB Output is correct
49 Correct 1337 ms 64312 KB Output is correct
50 Correct 1074 ms 64252 KB Output is correct
51 Correct 845 ms 63384 KB Output is correct
52 Correct 1310 ms 63928 KB Output is correct
53 Correct 1411 ms 64300 KB Output is correct
54 Correct 1202 ms 64308 KB Output is correct
55 Correct 1 ms 584 KB Output is correct
56 Execution timed out 4025 ms 63384 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 584 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Execution timed out 4054 ms 51460 KB Time limit exceeded
4 Halted 0 ms 0 KB -