Submission #972991

#	Time	Username	Problem	Language	Result	Execution time	Memory
972991		bachhoangxuan	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	905 ms	53076 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
const int maxl = 20;

int N,H[maxn],P[maxn],lt[maxn],rt[maxn];
int jmp[maxn][maxl],nxt[maxn][maxl],Max[maxn][maxl];

void init(int _N, vector<int> _H) {
    N=_N;
    for(int i=0;i<N;i++){
        H[i+1]=_H[i];
        P[H[i+1]]=i+1;
    }
    vector<int> v;
    for(int i=1;i<=N;i++){
        while(!v.empty() && H[v.back()]<H[i]) v.pop_back();
        rt[i]=(v.empty()?0:v.back());
        v.push_back(i);
    }
    v.clear();
    for(int i=N;i>=1;i--){
        while(!v.empty() && H[v.back()]<H[i]) v.pop_back();
        jmp[i][0]=lt[i]=(v.empty()?0:v.back());
        v.push_back(i);
        nxt[i][0]=(H[rt[i]]>H[lt[i]]?rt[i]:lt[i]);
        Max[i][0]=H[i];
    }
    for(int i=1;i<18;i++){
        for(int j=1;j<=N;j++){
            jmp[j][i]=jmp[jmp[j][i-1]][i-1];
            nxt[j][i]=nxt[nxt[j][i-1]][i-1];
        }
        for(int j=1;j<=N-(1<<i)+1;j++) Max[j][i]=max(Max[j][i-1],Max[j+(1<<(i-1))][i-1]);
    }
}

int dist(int l,int r){
    int cnt=0;
    for(int i=17;i>=0;i--){
        if(!jmp[l][i]) continue;
        if(jmp[l][i]<=r){
            cnt+=(1<<i);
            l=jmp[l][i];
        }
    }
    return cnt;
}

int query(int l,int r){
    int res=0;
    for(int i=0;i<18;i++) if((r-l+1)>>i&1){
        res=max(res,Max[l][i]);
        l+=(1<<i);
    }
    return res;
}
int get(int l,int r,int x){
    int res=0;
    for(int i=17;i>=0;i--){
        if((r-l+1)<(1<<i)) continue;
        int val=Max[r-(1<<i)+1][i];
        if(val>x) continue;
        res=max(res,val);
        r-=(1<<i);
    }
    return res;
}

int minimum_jumps(int A, int B, int C, int D) {
    A++;B++;C++;D++;
    int x=P[query(C,D)];
    int p=P[get(A,B,H[x])];
    if(!p) return -1;
    int m=P[query(p,C-1)];
    if(H[m]>H[x]) return -1;
    int l=lt[m],cnt=0;
    for(int i=17;i>=0;i--){
        int cc=nxt[p][i];
        if(!cc) continue;
        if(H[cc]<H[l]) cnt+=(1<<i),p=cc;
    }
    int val=dist(p,l);
    int r=rt[p];
    if(r && H[r]<H[x] && H[r]>H[l]) val=min(val,2);
    return cnt+val;
}

• 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