Submission #1216883

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216883		tapilyoca	Rainforest Jumps (APIO21_jumps)	C++20	4 / 100	1140 ms	74044 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
template<typename T>
using vec = vector<T>;
using ll = long long;


ll n, l;
vec<int> a;
vec<vec<int>> up, upR, upL;

void init(int N, std::vector<int> H) {
    n = N;
    a = H;
    up.assign(n,vec<int>(20,-1));
    upR.assign(n,vec<int>(20,-1));
    upL.assign(n,vec<int>(20,-1));

    stack<int> st;
    for(int i = 0; i < n; i++) {
        while(!st.empty() and a[st.top()] < a[i]) {
            upR[st.top()][0] = i;
            st.pop();
        }
        st.push(i);
    }

    while(!st.empty()) st.pop();
    for(int i = n - 1; i >= 0; i--) {
        while(!st.empty() and a[st.top()] < a[i]) {
            upL[st.top()][0] = i;
            st.pop();
        }
        st.push(i);
    }

    for(int i = 0; i < n; i++) {
        if(upR[i][0] == -1) upR[i][0] = i;
        if(upL[i][0] == -1) upL[i][0] = i;
    }

    for(int i = 0; i < n; i++) {
        up[i][0] = (a[upR[i][0]] > a[upL[i][0]] ? upR[i][0] : upL[i][0]);
    }

    for(int i = 1; i < 20; i++) {
        for(int v = 0; v < n; v++) {
            up[v][i] = up[up[v][i-1]][i-1];
            upL[v][i] = upL[upL[v][i-1]][i-1];
            upR[v][i] = upR[upR[v][i-1]][i-1];
        }
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    int at = B;

    // edge case: no middle 
    if(C == B+1) {
        if(upR[at][0] > D) return -1;
        return 1;
    }

    // find the midpeak
    int midPeak = B+1;
    for(int i = 19; i >= 0; i--) {
        if(upR[midPeak][i] < C) {
            midPeak = upR[midPeak][i];
        }
    }

    cerr << "Midpeak: " << midPeak << " w/ " << a[midPeak] << endl;

    // edge case: we are already taller than this
    if(a[B] >= a[midPeak]) {
        cerr << "Taller than mid, returning" << endl;
        if(upR[at][0] > D) return -1;
        return 1;
    }

    // find best starting point from this
    for(int i = 19; i >= 0; i--) {
        if(upL[at][i] >= A and a[upL[at][i]] < a[midPeak]) {
            at = upL[at][i];
        }
    }

    cerr << "New starting point: " << at << " w/ " << a[at] << endl;

    // edge case: next best peak brings us right there
    if(A <= upL[at][0] and upR[ upL[at][0] ][0] <= D and C <= upR[ upL[at][0] ][0]) {
        cerr << "Oh we can go back one and skip" << endl;
        return 1;
    }

    int ans = 0;
    cerr << "Stupid cases done, binlifting to mid" << endl;
    // binlift us up to mid yay
    for(int i = 19; i >= 0; i--) {
        if(a[up[at][i]] <= a[midPeak]) {
            at = up[at][i];
            ans += (1<<i);
        }
    }

    // if we are NOT at mid check the going left case
    if(at != midPeak) {
        if(upL[at][0] != at and upR[ upL[at][0] ][0] <= D) return ans + 2;
        return -1;
    }

    // check if we can make it from mid
    if(upR[at][0] <= D) return ans + 1;
    return -1;
}

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