oj.uz

Submission #553925

# Submission time Handle Problem Language Result Execution time Memory
553925 2022-04-27T10:47:10 Z Jarif_Rahman Rainforest Jumps (APIO21_jumps) C++17
23 / 100
 1153 ms 74840 KB 
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

struct sparse_table{
    vector<int> lg;
    vector<vector<pair<int, int>>> v;
    sparse_table(vector<int> _v){
        int n = _v.size();
        lg.resize(n+1);
        for(int i = 0; i <= n; i++) lg[i] = log2(i);
        int k = 0, p = 1;
        while(p < n) p*=2, k++;
        k++;
        v = vector<vector<pair<int, int>>>(n, vector<pair<int, int>>(k, make_pair(0, 0)));
        for(int i = 0; i < n; i++) v[i][0] = {_v[i], i};
        for(int p = 1; p < k; p++){
            for(int i = 0; i < n; i++){
                v[i][p] = max(v[i][p], v[i][p-1]);
                if(i + (1<<(p-1)) < n) v[i][p] = max(v[i][p], v[i + (1<<(p-1))][p-1]);
            }
        }
    }
    pair<int, int> query(int a, int b){
        int p = lg[b-a+1];
        return max(v[a][p], v[b-(1<<p)+1][p]);
    }
};

const int K = 21;
const int inf = 1e9;

int n;
vector<int> h;
vector<int> jump[2];
vector<int> anc[2][K];

sparse_table sp({});

template<int k>
int get_anc(int nd, int h){
    for(int i = 0; i < K; i++){
        if(h%2 == 1) nd = anc[k][i][nd];
        h/=2;
    }
    return nd;
}

template<int k>
int binlift(int nd, int l){
    if(h[nd] == l) return 0;
    if(h[nd] > l) return -inf;
    for(int i = K-1; i >= 0; i--) if(h[anc[k][i][nd]] <= l)
        return binlift<k>(anc[k][i][nd], l)+(1<<i);
    return 0;
}

void init(int N, vector<int> H){
    for(int &x: H) x--;
    n = N, h = H;
    h.pb(n);
    fill(jump, jump+2, vector<int>(n, n));
    fill(anc[0], anc[0]+K, vector<int>(n+1, n));
    fill(anc[1], anc[1]+K, vector<int>(n+1, n));

    sp = sparse_table(H);

    stack<int> st;
    for(int i = n-1; i >= 0; i--){
        while(!st.empty() && h[i] > h[st.top()]){
            jump[0][st.top()] = i;
            st.pop();
        }
        st.push(i);
    }
    while(!st.empty()) st.pop();

    for(int i = 0; i < n; i++){
        while(!st.empty() && h[i] > h[st.top()]){
            jump[1][st.top()] = i;
            st.pop();
        }
        st.push(i);
    }
    while(!st.empty()) st.pop();

    for(int i = 0; i < n; i++){
        anc[0][0][i] = h[jump[0][i]] < h[jump[1][i]] ? jump[0][i] : jump[1][i];
        anc[1][0][i] = h[jump[0][i]] > h[jump[1][i]] ? jump[0][i] : jump[1][i];
        if(anc[1][0][i] == n) anc[1][0][i] = anc[0][0][i];
    }

    for(int p = 1; p < K; p++) for(int i = 0; i <= n; i++)
        anc[0][p][i] = anc[0][p-1][anc[0][p-1][i]],
        anc[1][p][i] = anc[1][p-1][anc[1][p-1][i]];
}

int get_dis(int A, int C){
    int ans = binlift<1>(A, h[C]);
    if(ans < 0) return -1;
    int nd = get_anc<1>(A, ans);
    int x = binlift<0>(nd, h[C]);
    if(x < 0) return -1;
    nd = get_anc<0>(nd, x);
    ans+=x;
    if(nd == C) return ans;
    return -1;
}

int minimum_jumps(int A, int B, int C, int D){
    int l = 1, r = B-A+1;
    while(l < r){
        int md = (l+r)/2;
        if(sp.query(B-md+1, B).f > h[C]) r = md;
        else l = md+1;
    }
    int S = A;
    if(sp.query(B-l+1, B).f > h[C]){
        S = B-l+2;
        if(S > B) return -1;
        S = sp.query(S, B).sc;
    }
    return get_dis(S, C);
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 197 ms 34292 KB Output is correct
5 Correct 966 ms 74648 KB Output is correct
6 Correct 522 ms 12108 KB Output is correct
7 Correct 664 ms 74628 KB Output is correct
8 Correct 446 ms 25864 KB Output is correct
9 Correct 879 ms 74660 KB Output is correct
10 Correct 1074 ms 74680 KB Output is correct
11 Correct 1085 ms 74652 KB Output is correct
12 Correct 1025 ms 74552 KB Output is correct
13 Correct 890 ms 74552 KB Output is correct
14 Correct 902 ms 74660 KB Output is correct
15 Correct 875 ms 74660 KB Output is correct
16 Correct 816 ms 74680 KB Output is correct
17 Correct 0 ms 208 KB Output is correct
18 Correct 0 ms 208 KB Output is correct
19 Correct 2 ms 208 KB Output is correct
20 Correct 2 ms 336 KB Output is correct
21 Correct 2 ms 336 KB Output is correct
22 Correct 2 ms 336 KB Output is correct
23 Correct 2 ms 336 KB Output is correct
24 Correct 2 ms 336 KB Output is correct
25 Correct 0 ms 336 KB Output is correct
26 Correct 1 ms 464 KB Output is correct
27 Correct 14 ms 848 KB Output is correct
28 Correct 21 ms 848 KB Output is correct
29 Correct 9 ms 848 KB Output is correct
30 Correct 20 ms 848 KB Output is correct
31 Correct 19 ms 848 KB Output is correct
32 Correct 0 ms 208 KB Output is correct
33 Correct 74 ms 43236 KB Output is correct
34 Correct 117 ms 74784 KB Output is correct
35 Correct 111 ms 74660 KB Output is correct
36 Correct 131 ms 74668 KB Output is correct
37 Correct 109 ms 74660 KB Output is correct
38 Correct 125 ms 74656 KB Output is correct

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 197 ms 34292 KB Output is correct
5 Correct 966 ms 74648 KB Output is correct
6 Correct 522 ms 12108 KB Output is correct
7 Correct 664 ms 74628 KB Output is correct
8 Correct 446 ms 25864 KB Output is correct
9 Correct 879 ms 74660 KB Output is correct
10 Correct 1074 ms 74680 KB Output is correct
11 Correct 1085 ms 74652 KB Output is correct
12 Correct 1025 ms 74552 KB Output is correct
13 Correct 890 ms 74552 KB Output is correct
14 Correct 902 ms 74660 KB Output is correct
15 Correct 875 ms 74660 KB Output is correct
16 Correct 816 ms 74680 KB Output is correct
17 Correct 0 ms 208 KB Output is correct
18 Correct 0 ms 208 KB Output is correct
19 Correct 2 ms 208 KB Output is correct
20 Correct 2 ms 336 KB Output is correct
21 Correct 2 ms 336 KB Output is correct
22 Correct 2 ms 336 KB Output is correct
23 Correct 2 ms 336 KB Output is correct
24 Correct 2 ms 336 KB Output is correct
25 Correct 0 ms 336 KB Output is correct
26 Correct 1 ms 464 KB Output is correct
27 Correct 14 ms 848 KB Output is correct
28 Correct 21 ms 848 KB Output is correct
29 Correct 9 ms 848 KB Output is correct
30 Correct 20 ms 848 KB Output is correct
31 Correct 19 ms 848 KB Output is correct
32 Correct 0 ms 208 KB Output is correct
33 Correct 74 ms 43236 KB Output is correct
34 Correct 117 ms 74784 KB Output is correct
35 Correct 111 ms 74660 KB Output is correct
36 Correct 131 ms 74668 KB Output is correct
37 Correct 109 ms 74660 KB Output is correct
38 Correct 125 ms 74656 KB Output is correct
39 Correct 0 ms 208 KB Output is correct
40 Correct 0 ms 208 KB Output is correct
41 Correct 0 ms 208 KB Output is correct
42 Correct 263 ms 34164 KB Output is correct
43 Correct 907 ms 74664 KB Output is correct
44 Correct 607 ms 11980 KB Output is correct
45 Correct 932 ms 74680 KB Output is correct
46 Correct 551 ms 25868 KB Output is correct
47 Correct 942 ms 74660 KB Output is correct
48 Correct 1059 ms 74840 KB Output is correct
49 Correct 1098 ms 74780 KB Output is correct
50 Correct 1153 ms 74576 KB Output is correct
51 Correct 985 ms 74656 KB Output is correct
52 Correct 1064 ms 74660 KB Output is correct
53 Correct 904 ms 74680 KB Output is correct
54 Correct 833 ms 74624 KB Output is correct
55 Correct 0 ms 208 KB Output is correct
56 Correct 174 ms 74272 KB Output is correct
57 Incorrect 1032 ms 74552 KB Output isn't correct
58 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

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