Submission #549058

#	Time	Username	Problem	Language	Result	Execution time	Memory
549058		zaneyu	Rainforest Jumps (APIO21_jumps)	C++14	100 / 100	1100 ms	56064 KiB

jumps

/*input
7 3
1 2 3 4 5 6 7
4 4 6 6
1 3 5 6
0 1 2 2

*/
#include "jumps.h"

#include <cassert>
#include <cstdio>

#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
const int maxn=2e5+5;
#define sz(x) (int)x.size()
#define MNTO(x,y) x=min(x,(__typeof(x))y)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define pb push_back
const int INF=0x3f3f3f3f;
vector<int> v[maxn];
int n;
int pv[maxn],nxt[maxn];
int l[maxn][20],r[maxn][20],mx[maxn][20];
void init(int N, vector<int> arr) {
    n=N;
    vector<int> st;
    REP(i,n){
        while(sz(st) and arr[st.back()]<arr[i]){
            st.pop_back();
        }
        if(!sz(st)) pv[i]=-1;
        else pv[i]=st.back();
        st.pb(i);
    }
    st.clear();
    for(int i=n-1;i>=0;i--){
        while(sz(st) and arr[st.back()]<arr[i]){
            st.pop_back();
        }
        if(!sz(st)) nxt[i]=-1;
        else nxt[i]=st.back();
        st.pb(i);
    }
    REP(i,n){
        if(pv[i]==-1) mx[i][0]=nxt[i];
        else if(nxt[i]==-1) mx[i][0]=pv[i];
        else if(arr[nxt[i]]>arr[pv[i]]) mx[i][0]=nxt[i];
        else mx[i][0]=pv[i];
        l[i][0]=pv[i],r[i][0]=nxt[i];
    }
    REP1(j,18){
        REP(i,n){
            if(l[i][j-1]!=-1) l[i][j]=l[l[i][j-1]][j-1];
            else l[i][j]=-1;
            if(r[i][j-1]!=-1) r[i][j]=r[r[i][j-1]][j-1];
            else r[i][j]=-1;
            if(mx[i][j-1]!=-1) mx[i][j]=mx[mx[i][j-1]][j-1];
            else mx[i][j]=-1;
        }   
    }
}
int minimum_jumps(int A, int B, int C, int D) {
    int pos=B,ans=0;
    for(int i=18;i>=0;i--){
        if(l[pos][i]==-1) continue;
        if(l[pos][i]>=A and nxt[l[pos][i]]<=D and nxt[l[pos][i]]!=-1) pos=l[pos][i];
    }
    for(int i=18;i>=0;i--){
        if(mx[pos][i]==-1) continue;
        if(nxt[mx[pos][i]]!=-1 and nxt[mx[pos][i]]<C) ans+=(1<<i),pos=mx[pos][i];
    }
    if(nxt[pos]!=-1 and nxt[pos]<C and nxt[mx[pos][0]]<=D and nxt[mx[pos][0]]!=-1){
        ++ans;
        pos=mx[pos][0];
    }
    for(int i=18;i>=0;i--){
        if(r[pos][i]==-1) continue;
        if(r[pos][i]<C) pos=r[pos][i],ans+=(1<<i);
    }
    if(r[pos][0]>D or r[pos][0]==-1) return -1;
    return ans+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