Submission #1059268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059268		VMaksimoski008	Rainforest Jumps (APIO21_jumps)	C++17	33 / 100	4086 ms	35632 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 5;

int n, L[maxn][20], R[maxn][20];
vector<int> v;

void init(int N, vector<int> H) {
    n = N;
    v.push_back(1e9);
    for(int &x : H) v.push_back(x);
    v.push_back(1e9);

    stack<pair<int, int> > st; st.push({ 1e9, 0 });
    for(int i=1; i<=n; i++) {
        while(!st.empty() && st.top().first <= v[i]) st.pop();
        L[i][0] = st.top().second;
        st.push({ v[i], i });
    }

    while(!st.empty()) st.pop();

    st.push({ 1e9, n + 1 });
    for(int i=n; i>=1; i--) {
        while(!st.empty() && st.top().first <= v[i]) st.pop();
        R[i][0] = st.top().second;
        st.push({ v[i], i });
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    A++; B++; C++; D++;

    vector<int> dist(n+1), vis(n+1);
    queue<int> q;

    for(int i=A; i<=B; i++) vis[i] = 1, q.push(i);

    while(!q.empty()) {
        int u = q.front();
        q.pop();

        if(C <= u && u <= D) return dist[u];

        if(L[u][0] != 0 && !vis[L[u][0]]) {
            vis[L[u][0]] = 1;
            dist[L[u][0]] = dist[u] + 1;
            q.push(L[u][0]);
        }

        if(R[u][0] != n + 1 && !vis[R[u][0]]) {
            vis[R[u][0]] = 1;
            dist[R[u][0]] = dist[u] + 1;
            q.push(R[u][0]);
        }
    }

    return -1;
}

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