oj.uz

Submission #467754

# Submission time Handle Problem Language Result Execution time Memory
467754 2021-08-24T10:34:42 Z spike1236 Rainforest Jumps (APIO21_jumps) C++14
27 / 100
 1460 ms 56804 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ll long long
#define ld long double
#define all(_v) _v.begin(), _v.end()
#define sz(_v) (int)_v.size()
#define pii pair <int, int>
#define pll pair <ll, ll>
#define veci vector <int>
#define vecll vector <ll>

const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
const double PI = 3.1415926535897932384626433832795;
const double eps = 1e-9;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;

const int MAXN = 2e5 + 10;
int a[MAXN];
int L[MAXN], R[MAXN];
int n;
bool issorted;
int up_L[MAXN][22], up_R[MAXN][22], up_h[MAXN][22];
int dist[MAXN];

void init(int _n, veci _a) {
    n = _n;
    for(int i = 0; i < _n; ++i) a[i + 1] = _a[i];
    issorted = 1;
    for(int i = 1; i <= n; ++i)
        issorted &= (a[i] == 1 + a[i - 1]);
    a[0] = a[n + 1] = n + 1;
    stack <int> st;
    for(int i = 1; i <= n; ++i) {
        while(!st.empty() && a[st.top()] < a[i]) st.pop();
        if(!st.empty()) L[i] = st.top();
        else L[i] = 0;
        st.push(i);
    }
    while(!st.empty()) st.pop();
    for(int i = n; i > 0; --i) {
        while(!st.empty() && a[st.top()] < a[i]) st.pop();
        if(!st.empty()) R[i] = st.top();
        else R[i] = n + 1;
        st.push(i);
    }
    for(int i = 1; i <= n; ++i) {
        up_L[i][0] = L[i];
        up_R[i][0] = R[i];
        up_h[i][0] = (a[L[i]] > a[R[i]] ? L[i] : R[i]);
    }
    for(int j = 1; j < 20; ++j) {
        for(int i = 1; i <= n; ++i) {
            up_L[i][j] = up_L[up_L[i][j - 1]][j - 1];
            up_R[i][j] = up_R[up_R[i][j - 1]][j - 1];
            up_h[i][j] = up_h[up_h[i][j - 1]][j - 1];
        }
    }
}

int minimum_jumps_eq(int l, int x) {
    int ans = 0;
    for(int i = 19; i >= 0; --i)
        if(a[up_h[l][i]] <= a[x]) l = up_h[l][i], ans += (1 << i);
    if(a[L[l]] > a[x]) {
        for(int i = 19; i >= 0; --i)
            if(a[up_R[l][i]] <= a[x]) l = up_R[l][i], ans += (1 << i);
    } else {
        for(int i = 19; i <= 0; --i)
            if(a[up_L[l][i]] <= a[x]) l = up_L[l][i], ans += (1 << i);
    }
    return (l == x ? ans : -1);
}

int minimum_jumps(int l, int r, int x, int y) {
    ++l, ++r, ++x, ++y;
    if(issorted) return x - r;
    if(x == y) {
        for(int i = 19; i >= 0; --i)
            if(up_R[l][i] <= r && a[up_R[r][i]] < a[x]) l = up_R[l][i];
        return minimum_jumps_eq(l, x);
    }
    queue <int> q;
    for(int i = 1; i <= n; ++i) dist[i] = 1e9;
    for(int i = l; i <= r; ++i) {
        q.push(i);
        dist[i] = 0;
    }
    while(!q.empty()) {
        int v = q.front();
        q.pop();
        if(dist[L[v]] > dist[v] + 1) {
            dist[L[v]] = dist[v] + 1;
            q.push(L[v]);
        }
        if(dist[R[v]] > dist[v] + 1) {
            dist[R[v]] = dist[v] + 1;
            q.push(R[v]);
        }
    }
    int ans = 1e9;
    for(int i = x; i <= y; ++i) ans = min(ans, dist[i]);
    return (ans == 1e9 ? -1 : ans);
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 149 ms 45332 KB Output is correct
4 Correct 1263 ms 56640 KB Output is correct
5 Correct 967 ms 28604 KB Output is correct
6 Correct 715 ms 56604 KB Output is correct
7 Correct 904 ms 38844 KB Output is correct
8 Correct 1218 ms 56604 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Correct 106 ms 45352 KB Output is correct
6 Correct 136 ms 56116 KB Output is correct
7 Correct 65 ms 28832 KB Output is correct
8 Correct 123 ms 56588 KB Output is correct
9 Correct 15 ms 8708 KB Output is correct
10 Correct 125 ms 56056 KB Output is correct
11 Correct 119 ms 56604 KB Output is correct
12 Correct 137 ms 56512 KB Output is correct
13 Correct 136 ms 56480 KB Output is correct
14 Correct 126 ms 55980 KB Output is correct
15 Correct 159 ms 56188 KB Output is correct
16 Correct 127 ms 56584 KB Output is correct
17 Correct 130 ms 56524 KB Output is correct
18 Correct 1 ms 328 KB Output is correct
19 Correct 0 ms 328 KB Output is correct
20 Correct 1 ms 328 KB Output is correct
21 Incorrect 1 ms 328 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 338 ms 25732 KB Output is correct
5 Correct 1040 ms 55872 KB Output is correct
6 Correct 755 ms 9416 KB Output is correct
7 Correct 1196 ms 55840 KB Output is correct
8 Correct 511 ms 19400 KB Output is correct
9 Correct 1093 ms 55872 KB Output is correct
10 Correct 1051 ms 56700 KB Output is correct
11 Correct 1338 ms 56636 KB Output is correct
12 Correct 1243 ms 56640 KB Output is correct
13 Correct 1107 ms 55868 KB Output is correct
14 Correct 994 ms 56204 KB Output is correct
15 Correct 949 ms 56696 KB Output is correct
16 Correct 1228 ms 56604 KB Output is correct
17 Correct 0 ms 328 KB Output is correct
18 Correct 0 ms 328 KB Output is correct
19 Correct 2 ms 328 KB Output is correct
20 Correct 3 ms 328 KB Output is correct
21 Correct 3 ms 328 KB Output is correct
22 Correct 3 ms 328 KB Output is correct
23 Correct 3 ms 328 KB Output is correct
24 Correct 3 ms 328 KB Output is correct
25 Correct 0 ms 328 KB Output is correct
26 Correct 1 ms 548 KB Output is correct
27 Correct 26 ms 840 KB Output is correct
28 Correct 26 ms 840 KB Output is correct
29 Correct 23 ms 840 KB Output is correct
30 Correct 17 ms 840 KB Output is correct
31 Correct 21 ms 904 KB Output is correct
32 Correct 0 ms 328 KB Output is correct
33 Correct 70 ms 32416 KB Output is correct
34 Correct 140 ms 55972 KB Output is correct
35 Correct 119 ms 56476 KB Output is correct
36 Correct 121 ms 55844 KB Output is correct
37 Correct 163 ms 56316 KB Output is correct
38 Correct 121 ms 56696 KB Output is correct

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 338 ms 25732 KB Output is correct
5 Correct 1040 ms 55872 KB Output is correct
6 Correct 755 ms 9416 KB Output is correct
7 Correct 1196 ms 55840 KB Output is correct
8 Correct 511 ms 19400 KB Output is correct
9 Correct 1093 ms 55872 KB Output is correct
10 Correct 1051 ms 56700 KB Output is correct
11 Correct 1338 ms 56636 KB Output is correct
12 Correct 1243 ms 56640 KB Output is correct
13 Correct 1107 ms 55868 KB Output is correct
14 Correct 994 ms 56204 KB Output is correct
15 Correct 949 ms 56696 KB Output is correct
16 Correct 1228 ms 56604 KB Output is correct
17 Correct 0 ms 328 KB Output is correct
18 Correct 0 ms 328 KB Output is correct
19 Correct 2 ms 328 KB Output is correct
20 Correct 3 ms 328 KB Output is correct
21 Correct 3 ms 328 KB Output is correct
22 Correct 3 ms 328 KB Output is correct
23 Correct 3 ms 328 KB Output is correct
24 Correct 3 ms 328 KB Output is correct
25 Correct 0 ms 328 KB Output is correct
26 Correct 1 ms 548 KB Output is correct
27 Correct 26 ms 840 KB Output is correct
28 Correct 26 ms 840 KB Output is correct
29 Correct 23 ms 840 KB Output is correct
30 Correct 17 ms 840 KB Output is correct
31 Correct 21 ms 904 KB Output is correct
32 Correct 0 ms 328 KB Output is correct
33 Correct 70 ms 32416 KB Output is correct
34 Correct 140 ms 55972 KB Output is correct
35 Correct 119 ms 56476 KB Output is correct
36 Correct 121 ms 55844 KB Output is correct
37 Correct 163 ms 56316 KB Output is correct
38 Correct 121 ms 56696 KB Output is correct
39 Correct 0 ms 328 KB Output is correct
40 Correct 0 ms 328 KB Output is correct
41 Correct 0 ms 328 KB Output is correct
42 Correct 270 ms 25620 KB Output is correct
43 Correct 1127 ms 55868 KB Output is correct
44 Correct 762 ms 9416 KB Output is correct
45 Correct 1088 ms 55988 KB Output is correct
46 Correct 680 ms 19396 KB Output is correct
47 Correct 997 ms 55832 KB Output is correct
48 Correct 1121 ms 56692 KB Output is correct
49 Correct 1294 ms 56628 KB Output is correct
50 Correct 1167 ms 56512 KB Output is correct
51 Correct 1401 ms 55868 KB Output is correct
52 Correct 1460 ms 56240 KB Output is correct
53 Correct 1068 ms 56804 KB Output is correct
54 Correct 1116 ms 56596 KB Output is correct
55 Correct 0 ms 328 KB Output is correct
56 Incorrect 221 ms 55672 KB Output isn't correct
57 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 149 ms 45332 KB Output is correct
4 Correct 1263 ms 56640 KB Output is correct
5 Correct 967 ms 28604 KB Output is correct
6 Correct 715 ms 56604 KB Output is correct
7 Correct 904 ms 38844 KB Output is correct
8 Correct 1218 ms 56604 KB Output is correct
9 Correct 0 ms 328 KB Output is correct
10 Correct 0 ms 328 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 1 ms 328 KB Output is correct
13 Incorrect 1 ms 328 KB Output isn't correct
14 Halted 0 ms 0 KB -