Submission #1201146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201146		guagua0407	Rainforest Jumps (APIO21_jumps)	C++20	23 / 100	4030 ms	36404 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 chmax(int a,int b){
        return (h[a]>h[b]?a:b);
    }
}
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];
    }
    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';
        }
    }
}
int minimum_jumps(int A, int B, int C, int D) {
    A++, B++, C++, D++;
    int mn=1e9;
    for(int t=A;t<=B;t++){
        int ans = 0;
        int x=t;
        for(int i = 19; i >= 0; i--){
            int y=o[i][x];
            //cout << nl << ' ' << nr << '\n';
            if(h[y] < h[C]){
                ans += (1 << i);
                x=y;
                //cout<<L<<' '<<R<<'\n';
            }
        }
        //cout<<L<<' '<<R<<'\n';
        for(int i = 19; i >= 0; i--){
            int y=R[i][x];
            //cout << nl << ' ' << nr << '\n';
            if(h[y] < h[C]){
                ans += (1 << i);
                x=y;
            }
        }
        //cout << r[0][R] << ' ' << r[0][L] << '\n';;
        if(r[x]>=C and r[x]<=D){
            mn=min(mn,ans+1);
        }
    }
    return (mn==1e9?-1:mn);
}
/*
6 1
5 1 2 3 4 6
1 1 4 4

*/

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 23 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19