Submission #1161178

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161178		just	Rainforest Jumps (APIO21_jumps)	C++20	37 / 100	4053 ms	13908 KiB

jumps

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

#define all(x) (x).begin(), (x).end()
#define int long long
#define vec vector
#define pii pair<int, int>

#define X first
#define Y second

const int BIG = 1e18;

int n;
vec<int> heights;

vec<int> lst, nxt;

bool monotonic = true;

void init(signed N, vec<signed> H) {
    {
        n = N;
        assert(H.size() == n);
    
        heights.resize(n);
        for (int i = 0; i < n; i++) {
            heights[i] = H[i];
        }
    }
    

    for (int i = 0; i < n; i++) monotonic &= heights[i] == i + 1;


    lst.resize(n);
    nxt.resize(n);
    
    {
        stack<int> st;
        for (int i = 0; i < n; i++) {
            while (!st.empty() && heights[st.top()] <= heights[i])
                st.pop();
            lst[i] = st.empty() ? -1 : st.top();
            st.push(i);
        }
    }
    
    {
        stack<int> st;
        for (int i = n - 1; i >= 0; i--) {
            while (!st.empty() && heights[st.top()] <= heights[i])
                st.pop();
            nxt[i] = st.empty() ? n : st.top();
            st.push(i);
        }
    }
}

int a, b, c, d;

int  DATA[200'200];
bool SEEN[200'200];
int dfs(int x) {
    if (c <= x && x <= d) return 0;

    if (SEEN[x]) return DATA[x];
    SEEN[x] = 1;

    if (lst[x] == -1 && nxt[x] == n) return DATA[x] = BIG;
    if (lst[x] == -1) return DATA[x] = dfs(nxt[x]) + 1;
    if (nxt[x] ==  n) return DATA[x] = dfs(lst[x]) + 1;
    return DATA[x] = min(dfs(lst[x]), dfs(nxt[x])) + 1;
}

int calc() {
    if (monotonic) { return c - b; };

    memset(SEEN, 0, sizeof(SEEN));
    
    int ans = BIG;
    for (int i = a; i <= b; i++) {
        ans = min(ans, dfs(i));
    }

    return ans == BIG ? -1 : ans;
}

signed minimum_jumps(signed _A, signed _B, signed _C, signed _D) {
    a = _A, b = _B, c = _C, d = _D;
    return calc();
}


#ifdef debug
signed main() {}
#endif

• Subtask 1: 4 / 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