Submission #1201407

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201407		guagua0407	Rainforest Jumps (APIO21_jumps)	C++20	100 / 100	502 ms	49644 KiB

jumps

#include<bits/stdc++.h>
using namespace std;
#include "jumps.h"
//#include "stub.cpp"
#define F first
#define S second
#define double long double
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
#define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
namespace{
    const int mxn = 2e5 + 5;
    int l[mxn],r[mxn];
    int n, h[mxn], o[20][mxn], R[20][mxn];
    int T[20][mxn];
    int chmax(int a,int b){
        return (h[a]>h[b]?a:b);
    }
    int get(int l,int r){
        int g=__lg(r-l+1);
        return chmax(T[g][l],T[g][r-(1<<g)+1]);
    }
}
void init(int N, std::vector<int> H) {
    n = N;
    h[0] = 2e9, h[n + 1] = 2e9;
    for(int i = 1; i <= n; i++){
        h[i] = H[i - 1];
    }
    vector<int>st;
    st.pb(0);
    for(int i = 1; i <= n ; i++){
        while(sz(st) and h[st.back()] < h[i]) st.pop_back();
        l[i] = st.back();
        st.pb(i);
    }
    st.clear();
    st.pb(n + 1);
    R[0][n + 1] = n + 1;
    o[0][n + 1] = n + 1;
    for(int i = n ; i > 0; i--){
        while(sz(st) and h[st.back()] < h[i]) st.pop_back();
        r[i] = st.back();
        st.pb(i);
    }
    for(int j=0;j<=n;j++){
        o[0][j]=chmax(l[j],r[j]);
        R[0][j]=r[j];
        T[0][j]=j;
    }
    for(int i = 1; i < 20; i++){
        for(int j = 0; j <= n + 1; j++){
            o[i][j] = chmax(o[i-1][o[i-1][j]], o[i-1][o[i-1][j]]);
            R[i][j] = R[i-1][R[i-1][j]];
            //cout << i << ' ' << j << ' ' << l[i][j] << ' ' << r[i][j] << '\n';
        }
    }
    for(int i=1;i<20;i++){
        for(int j=0;j+(1<<i)-1<=n+1;j++){
            //cout<<j+(1<<(i-1))<<'\n';
            T[i][j]=chmax(T[i-1][j],T[i-1][j+(1<<(i-1))]);
        }
    }
}
int minimum_jumps(int A, int B, int C, int D) {
    A++, B++, C++, D++;
    int mx=get(C,D);
    int mx2=get(B,C-1);
    if(h[mx2]>h[mx]) return -1;
    int tl=A,tr=B;
    while(tl<tr){
        int mid=(tl+tr)/2;
        if(h[get(mid,B)]<h[mx]){
            tr=mid;
        }
        else{
            tl=mid+1;
        }
    }
    int x=get(tl,B);
    int ans = 0;
    for(int i = 19; i >= 0; i--){
        int y=o[i][x];
        //cout << nl << ' ' << nr << '\n';
        if(h[y] < h[mx2]){
            ans += (1 << i);
            x=y;
            //cout<<L<<' '<<R<<'\n';
        }
    }
    //cout<<x<<' '<<ans<<'\n';
    if(h[x]>=h[mx2]) return ans+1;
    if(h[o[0][x]]<=h[mx]) return ans+2;
    //cout<<L<<' '<<R<<'\n';
    for(int i = 19; i >= 0; i--){
        int y=R[i][x];
        //cout << nl << ' ' << nr << '\n';
        if(y<C){
            //cout<<y<<' '<<mx<<'\n';
            ans += (1 << i);
            x=y;
        }
    }
    //cout<<x<<' '<<ans<<'\n';
    //cout << r[0][R] << ' ' << r[0][L] << '\n';;
    return ans+1;
}
/*
6 1
5 1 2 3 4 6
1 1 4 4

*/

• 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