Submission #1282300

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282300		StefanSebez	Rainforest Jumps (APIO21_jumps)	C++20	100 / 100	422 ms	51312 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
const int N=2e5+50,inf=1e9,lg=18;
int n,a[N],ind[N],Lv[N],Rv[N],par[N][lg+1],par2[N][lg+1];
int Maks[N][lg+1],LOG[N+50];
int Get(int l,int r){if(l>r)return 0;int i=LOG[r-l+1];return max(Maks[l][i],Maks[r-(1<<i)+1][i]);}
void init(int n1,vector<int>H){
    n=n1;for(int i=1;i<=n;i++) a[i]=H[i-1];
    vector<int>mono;
    for(int i=1;i<=n;i++){
        while(!mono.empty()&&a[mono.back()]<a[i]){
            Rv[mono.back()]=i;
            mono.pop_back();
        }
        if(!mono.empty()) Lv[i]=mono.back();
        mono.pb(i);
    }
    a[0]=inf;
    for(int i=1;i<=n;i++){
        if(Lv[i]==0) par[i][0]=Rv[i];
        else if(Rv[i]==0) par[i][0]=Lv[i];
        else if(a[Lv[i]]>a[Rv[i]]) par[i][0]=Lv[i];
        else par[i][0]=Rv[i];
        par2[i][0]=Rv[i];
    }
    for(int j=1;j<=lg;j++){
        for(int i=1;i<=n;i++){
            par[i][j]=par[par[i][j-1]][j-1];
            par2[i][j]=par2[par2[i][j-1]][j-1];
        }
    }
    for(int i=1;i<=n;i++) ind[a[i]]=i;
    for(int i=1;i<=n;i++) Maks[i][0]=a[i];
    for(int i=1,e=1,ct=-1;i<=N;i++){if(i==e)e<<=1,ct++;LOG[i]=ct;}
    for(int j=0;j<lg;j++){
        for(int i=1;i<=n;i++){
            if(i+(1<<j)<=n) Maks[i][j+1]=max(Maks[i][j],Maks[i+(1<<j)][j]);
        }
    }
}
int minimum_jumps(int A, int B, int C, int D) {
    A++,B++,C++,D++;
    int X=Get(B,C-1),Y=Get(C,D);
    if(X>Y) return -1;
    int l=A,r=B,val=0;
    while(l<=r){
        int mid=l+r>>1;
        int x=Get(mid,B);
        if(Get(mid,B)<Y){r=mid-1;val=x;}
        else l=mid+1;
    }
    int u=ind[val],res=0;
    for(int i=lg;i>=0;i--){
        if(par[u][i]&&a[par[u][i]]<X){
            u=par[u][i];
            res+=1<<i;
        }
    }
    if(Rv[u]>=C) return res+1;
    if(par[u][0]&&a[par[u][0]]<Y) return res+2;
    for(int i=lg;i>=0;i--){
        if(par2[u][i]&&par2[u][i]<C){
            u=par2[u][i];
            res+=1<<i;
        }
    }
    return res+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