Submission #1161175

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161175		just	Rainforest Jumps (APIO21_jumps)	C++20	0 / 100	4070 ms	1114112 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);

    for (int i = 0; i < n; i++) {
        int x = heights[i];
        
        lst[x] = -1;
        nxt[x] =  n;

        for(int j = i - 1; j >= 0; j--) {
            if (heights[j]  > x) {
                lst[x] = j;
                break;
            }
        }

        for(int j = i + 1; j < n; j++) {
            if (heights[j] > x) {
                nxt[x] = j;
                break;
            }
        }
    }
}

int a, b, c, d;

int dfs(int x) {
    if (c <= x && x <= d) return 0;

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

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

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