제출 #1161250

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1161250		just	Rainforest Jumps (APIO21_jumps)	C++20	25 / 100	4032 ms	10588 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 dfs_opt(int x, int t) {
    if (x == t) return 0;

    if (lst[x] == -1 && nxt[x] == n) {
        return BIG;
    } else if (lst[x] == -1) {
        return dfs_opt(nxt[x], t) + 1;
    } else if (nxt[x] == n) {
        return dfs_opt(lst[x], t) + 1;
    } else {
        int h = heights[t], l = heights[lst[x]], r = heights[nxt[x]];
        if (l <= h && r <= h) {
            if (l > r) {
                return dfs_opt(lst[x], t) + 1;
            } else {
                return dfs_opt(nxt[x], t) + 1;
            }
        } else if (l <= h) {
            return dfs_opt(lst[x], t) + 1;
        } else if (r <= h) {
            return dfs_opt(nxt[x], t) + 1;
        } else {
            return BIG;
        }
    }
}

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

    memset(SEEN, 0, sizeof(SEEN));

    if (c == d) {
        int ans = BIG;
        for (int i = a; i <= b; i++) {
            ans = min(ans, dfs_opt(i, c));
        }
        return ans >= BIG ? -1 : ans;
    }
    
    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: 0 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19