Submission #1080285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080285		alexander707070	Rainforest Jumps (APIO21_jumps)	C++14	23 / 100	891 ms	52128 KiB

jumps

#include<bits/stdc++.h>
#include "jumps.h"

#define MAXN 200007
using namespace std;

int n,h[MAXN],pr[MAXN],nxt[MAXN];
stack<int> st;

int upleft[MAXN][20],upright[MAXN][20],up[MAXN][20];

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

        pr[i]=st.top();
        st.push(i);
    }

    while(!st.empty())st.pop();

    st.push(n+1); nxt[n+1]=n+1;
    for(int i=n;i>=1;i--){
        while(!st.empty() and h[i]>h[st.top()]){
            st.pop();
        }

        nxt[i]=st.top();
        st.push(i);
    }
}

int best(int x,int y){
    if(h[x]>h[y])return x;
    return y;
}

void calclift(){
    for(int i=0;i<20;i++){
        for(int f=0;f<=n+1;f++){
            if(i==0){
                upleft[f][0]=pr[f];
                upright[f][0]=nxt[f];
                up[f][0]=best(pr[f],nxt[f]);
            }else{
                upleft[f][i]=upleft[upleft[f][i-1]][i-1];
                upright[f][i]=upright[upright[f][i-1]][i-1];
                up[f][i]=up[up[f][i-1]][i-1];
            }
        }
    }
}

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

    calcstack();
    calclift();
}

int minimum_jumps(int A, int B, int C, int D){
    int ans=0; 
    A++; B++; C++; D++;

    for(int i=19;i>=0;i--){
        if(h[up[A][i]]<=h[C]){
            A=up[A][i];
            ans+=(1<<i);
        }
    }

    for(int i=19;i>=0;i--){
        if(h[upright[A][i]]<=h[C]){
            A=upright[A][i];
            ans+=(1<<i);
        }
    }

    if(A!=C)return -1;

    return ans;
}

/*int main(){
    init(7, {3, 2, 1, 6, 4, 5, 7});

    cout<<minimum_jumps(4, 4, 6, 6)<<"\n";
}*/

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 23 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19