Submission #480443

#	Time	Username	Problem	Language	Result	Execution time	Memory
480443		dantoh000	Rainforest Jumps (APIO21_jumps)	C++14	100 / 100	1483 ms	45208 KiB

jumps

#include "jumps.h"

#include <bits/stdc++.h>
using namespace std;
vector<int> R[18], L[18], U[18];

void init(int N, std::vector<int> H) {
    for (int i = 0; i < 18; i++){
        R[i].resize(N);
        L[i].resize(N);
        U[i].resize(N);
    }

    stack<int> st;
    for (int i = 0; i < N; i++){
        while (st.size() && H[st.top()] < H[i]){
            st.pop();
        }
        if (st.empty()) L[0][i] = -1;
        else L[0][i] = st.top();
        st.push(i);
    }
    while (st.size()) st.pop();
    for (int i = N-1; i >= 0; i--){
        while (st.size() && H[st.top()] < H[i]){
            st.pop();
        }
        if (st.empty()) R[0][i] = -1;
        else R[0][i] = st.top();
        st.push(i);
    }
    for (int i = 0; i < N; i++){
        if (L[0][i] == -1) U[0][i] = R[0][i];
        else if (R[0][i] == -1) U[0][i] = L[0][i];
        else U[0][i] = H[L[0][i]] > H[R[0][i]] ? L[0][i] : R[0][i];
    }
    for (int k = 1; k < 18; k++){
        for (int i = 0; i < N; i++){
            if (U[k-1][i] == -1) U[k][i] = -1;
            else U[k][i] = U[k-1][U[k-1][i]];
            if (L[k-1][i] == -1) L[k][i] = -1;
            else L[k][i] = L[k-1][L[k-1][i]];
            if (R[k-1][i] == -1) R[k][i] = -1;
            else R[k][i] = R[k-1][R[k-1][i]];
        }
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    int s = B;
    for (int k = 17; k >= 0; k--){
        if (L[k][s] != -1 && L[k][s] >= A && R[0][L[k][s]] != -1 && R[0][L[k][s]] <= D){
            s = L[k][s];
        }
    }
    int ans = 0;
    for (int k = 17; k >= 0; k--){
        if (U[k][s] != -1 && R[0][U[k][s]] != -1 && R[0][U[k][s]] < C){
            s = U[k][s];
            ans += (1<<k);
        }
    }
    if (U[0][s] != -1 && R[0][s] != -1 && R[0][s] < C && R[0][U[0][s]] != -1 && R[0][U[0][s]] <= D){
        ans++;
        s = U[0][s];
    }
    for (int k = 17; k >= 0; k--){
        if (R[k][s] != -1 && R[k][s] < C){
            s = R[k][s];
            ans += (1<<k);
        }
    }
    if (R[0][s] == -1 || R[0][s] > D) 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