Submission #1197013

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197013		NoMercy	Rainforest Jumps (APIO21_jumps)	C++20	81 / 100	4094 ms	50544 KiB

jumps

#include "jumps.h"

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

const int lg = 20, MAXN = 2e5 + 55;
int up[lg][MAXN][3], N, H[MAXN];

bool sub1 = true;

void init(int n, vector<int> h) {
    N = n;
    H[0] = H[N + 1] = 1e9 + 7;
    for (int i = 1;i <= N;i ++) H[i] = h[i - 1], sub1 &= (H[i] == i);
    
    N += 2;
    stack<int> st;
    for (int i = 0; i < N; ++i) {
        while (!st.empty() && H[st.top()] <= H[i]) st.pop();

        if (st.size() > 0) up[0][i][0] = st.top();
        else up[0][i][0] = i;
        st.push(i);
    } while (!st.empty()) st.pop();

    for (int i = N - 1; i >= 0; --i) {
        while (!st.empty() && H[st.top()] <= H[i]) st.pop();

        if (st.size() > 0) up[0][i][1] = st.top();
        else up[0][i][1] = i;
        st.push(i);
    }
    for (int i = 0; i < N; ++i) {
        up[0][i][2] = H[up[0][i][0]] > H[up[0][i][1]] ? up[0][i][0] : up[0][i][1];
    }

    for (int bt = 1;bt < lg;bt ++) {
        for (int i = 0;i < N;i ++) {
            up[bt][i][0] = up[bt - 1][up[bt - 1][i][0]][0];
            up[bt][i][1] = up[bt - 1][up[bt - 1][i][1]][1];
            up[bt][i][2] = up[bt - 1][up[bt - 1][i][2]][2];
        }
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    A ++; B ++; C ++; D ++;
    if (sub1 == true) {
        return C - B;
    }
    
    int res = 1e9 + 7;
    for (int ind = C;ind <= D;ind ++) {
        int _B = B;
        for (int bt = lg - 1;bt >= 0;bt --) {
            if (A <= up[bt][B][0] && H[up[bt][B][0]] < H[ind]) {
                B = up[bt][B][0];
            }
        }
        int cnt = 0;
        for (int bt = lg - 1;bt >= 0;bt --) {
            if (H[up[bt][B][2]] <= H[ind]) {
                B = up[bt][B][2];
                cnt += (1 << bt);
            }
        }

        if (H[up[0][B][0]] > H[ind]) {
            for (int bt = lg - 1;bt >= 0;bt --) {
                if (H[up[bt][B][1]] <= H[ind]) {
                    B = up[bt][B][1];
                    cnt += (1 << bt);
                }
            }
        } else {
            for (int bt = lg - 1;bt >= 0;bt --) {
                if (H[up[bt][B][0]] <= H[ind]) {
                    B = up[bt][B][0];
                    cnt += (1 << bt);
                }
            }
        }
        if (ind == B) {
            res = min(res, cnt);
        }
        B = _B;
    }
    if (res == 1e9 + 7) return -1;

    return res;
}

• 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: 0 / 19