제출 #1216658

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1216658		tapilyoca	Rainforest Jumps (APIO21_jumps)	C++20	0 / 100	87 ms	22736 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
template<typename T>
using vec = vector<T>;
using ll = long long;


ll n, l;
vec<int> a;
vec<int> jumpRight, jumpLeft;
vec<vec<int>> up;

void init(int N, std::vector<int> H) {
    n = N;
    a = H;
    jumpRight.assign(n,-1);
    jumpLeft.assign(n,-1);
    up.assign(n,vec<int>(20,-1));

    stack<int> st;
    for(int i = 0; i < n; i++) {
        while(!st.empty() and a[st.top()] < a[i]) {
            jumpRight[st.top()] = i;
            st.pop();
        }
        st.push(i);
    }

    while(!st.empty()) st.pop();
    for(int i = n - 1; i >= 0; i--) {
        while(!st.empty() and a[st.top()] < a[i]) {
            jumpLeft[st.top()] = i;
            st.pop();
        }
        st.push(i);
    }

    for(int i = 0; i < n; i++) {
        // get optimal: move left or move right
        int lj = jumpLeft[i], rj = jumpRight[i];
        if(lj == -1 and rj == -1) continue;
        else if(lj == -1) up[i][0] = rj;
        else if(rj == -1) up[i][0] = lj;
        else {
            if(a[lj] > a[rj]) {
                up[i][0] = lj;
            } else {
                up[i][0] = rj;
            }
        }
    }

    for(int i = 1; i < 20; i++) {
        for(int v = 0; v < n; v++) {
            if(up[v][i-1] == -1) continue;
            up[v][i] = up[up[v][i-1]][i-1];
        }
    }

}

int minimum_jumps(int A, int B, int C, int D) {
    assert(A == B && C == D);

    int at = A;
    int hLim = a[C];
    int ans = 0;

    for(int i = 19; i >= 0; i--) {
        if(up[at][i] == -1) continue;
        if(a[up[at][i]] < hLim) {
            ans += (1<<i);
            at = up[at][i];
        }
    }

    if(up[at][0] == C) return ans+1;
    else return -1;
}

• 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