Submission #569255

#	Time	Username	Problem	Language	Result	Execution time	Memory
569255		ryangohca	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	1140 ms	50504 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
 
int heights[200002], N;
int L[200002][20], R[200002][20], high[200002][20];
 
 
void init(int N, vector<int> H) {
    ::N = N;
    heights[0] = heights[N+1] = 6969420;
    for (int i = 0; i < N; i++){
        heights[i+1] = H[i];
    }
    
    stack<int> idx; idx.push(0);
    for (int i = 1; i <= N; i++){
        while (heights[idx.top()] < heights[i]) idx.pop();
        L[i][0] = idx.top();
        idx.push(i);
    }
    
    stack<int> idx2; idx2.push(N+1);
    for (int i = N; i >= 1; i--){
        while (heights[idx2.top()] < heights[i]) idx2.pop();
        R[i][0] = idx2.top();
        idx2.push(i);
        high[i][0] = ((heights[L[i][0]] > heights[R[i][0]]) ? L[i][0] : R[i][0]);
    }
    
    R[N+1][0] = N+1;
    for (int p = 1; p <= 19; p++){
        R[N+1][p] = N+1;
        for (int i = 1; i <= N; i++){
            L[i][p] = L[L[i][p-1]][p-1];
            R[i][p] = R[R[i][p-1]][p-1];
            high[i][p] = high[high[i][p-1]][p-1];
        }
    }
}
 
int minimum_jumps(int A, int B, int C, int D) {
    A++; B++; C++; D++;
    int furthest = B;
    for (int i = 19; i >= 0; i--){
        if (R[furthest][i] < C) furthest = R[furthest][i];
    }
    if (furthest == B){
        if (R[B][0] <= D) return 1;
        //else return -1;
    }
    int st = B;
    for (int i = 19; i >= 0; i--){
        if (L[st][i] >= A && heights[L[st][i]] < heights[furthest]) st = L[st][i];
    }
    if (L[st][0] >= A && R[L[st][0]][0] <= D) return 1;
    int cur = st;
    int ans = 0;
    for (int i = 19; i >= 0; i--){
        if (heights[high[cur][i]] <= heights[furthest]) {
            cur = high[cur][i];
            ans += 1 << i;
        }
    } 
    if (R[cur][0] >= C && R[cur][0] <= D) return ans+1;
    if (L[cur][0] != 0 && R[L[cur][0]][0] <= D) return ans+2;
    for (int i = 19; i >= 0; i--){
        if (R[cur][i] < C){
            cur = R[cur][i];
            ans += 1 << i;
        } 
    }
    if (R[cur][0] <= D) return ans+1;
    else return -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