Submission #1080326

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080326		alexander707070	Rainforest Jumps (APIO21_jumps)	C++14	100 / 100	948 ms	52272 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++;
    int maxs=C;

    for(int i=19;i>=0;i--){
        if(upright[maxs][i]<=D){
            maxs=upright[maxs][i];
        }
    }

    for(int i=19;i>=0;i--){
        if(h[upleft[B][i]]<=h[maxs] and upleft[B][i]>=A){
            B=upleft[B][i];
        }
    }

    A=B;

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

    if(h[up[A][0]]<=h[maxs] and nxt[A]<C){
        A=up[A][0]; ans++;
    }

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

    A=nxt[A];
    ans++;

    if(A<C or A>D)return -1;

    return ans;
}

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

    cout<<minimum_jumps(4, 4, 6, 6)<<"\n";
    cout<<minimum_jumps(1, 3, 5, 6)<<"\n";
    cout<<minimum_jumps(0, 1, 2, 2)<<"\n";
}*/

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