Submission #1203254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203254		Francisco_Martin	Rainforest Jumps (APIO21_jumps)	C++20	100 / 100	536 ms	98440 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll N; const ll INF=1e9;
vector<int> H; vector<vector<ll>> L, R, hi;

void init(int N_,vector<int> H_){
    H=H_; H.insert(H.begin(),INF); H.insert(H.end(),INF);
    N=N_+2; L=R=hi=vector<vector<ll>>(20,vector<ll>(N));
    stack<ll> stk, stk2;
    for(int i=0; i<N; i++){
        while(!stk.empty() && H[stk.top()]<=H[i]) stk.pop();
        if(stk.empty()) L[0][i]=i;
        else L[0][i]=stk.top();
        stk.push(i);
    }
    for(int i=N-1; i>=0; i--){
        while(!stk2.empty() && H[stk2.top()]<=H[i]) stk2.pop();
        if(stk2.empty()) R[0][i]=i;
        else R[0][i]=stk2.top();
        stk2.push(i);
    }
    for(int i=0; i<N; i++){
        if(H[L[0][i]]>H[R[0][i]]) hi[0][i]=L[0][i];
        else hi[0][i]=R[0][i];
    }
    for(int i=1; i<20; i++){
        for(int j=0; j<N; j++){
            L[i][j]=L[i-1][L[i-1][j]];
            R[i][j]=R[i-1][R[i-1][j]];
            hi[i][j]=hi[i-1][hi[i-1][j]];
        }
    }
}

int minimum_jumps(int A,int B,int C,int D) {
    ll ans=0; A++; B++; C++; D++;
    auto query=[&](ll l,ll r){
        for(int i=19; i>=0; i--){
            if(R[i][l]<=r) l=R[i][l];
        }
        return l;
    };
    if(B==C-1){
        if(R[0][B]<=D) return 1;
        else return -1;
    }
    ll x=query(B+1,C-1);
    if(H[B]>H[x]){
        if(R[0][B]<=D) return 1;
        else return -1;
    }
    for(int i=19; i>=0; i--){
        if(A<=L[i][B] && H[L[i][B]]<H[x]) B=L[i][B];
    }
    if(A<=L[0][B]){
        if(R[0][L[0][B]]<=D) return 1;
    }else{
        for(int i=19; i>=0; i--){
            if(H[hi[i][B]]<=H[x]){
                ans|=(1<<i);
                B=hi[i][B];
            }
        }
        if(B==x){
            if(R[0][B]<=D) return ans+1;
            else return -1;
        }
        if(0<L[0][B] && R[0][L[0][B]]<=D) return ans+2;
    }
    for(int i=19; i>=0; i--){
        if(R[i][B]<C){
            ans+=(1<<i);
            B=R[i][B];
        }
    }
    if(C<=R[0][B] && R[0][B]<=D) return ans+1;
    else return -1;
}

• 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