제출 #593036

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
593036		Jomnoi	밀림 점프 (APIO21_jumps)	C++17	37 / 100	4051 ms	6584 KiB

jumps

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

const int MAX_N = 2e5 + 5;
const int INF = 1e9 + 7;

int N;
bool subtask1;
int H[MAX_N], L[MAX_N], R[MAX_N], dp[MAX_N];
vector <pair <int, int>> trees;

void init(int n, vector <int> h) {
    N = n;
    subtask1 = true;
    for(int i = 1; i <= N; i++) {
        H[i] = h[i - 1];
        trees.emplace_back(H[i], i);

        if(H[i] < H[i - 1]) {
            subtask1 = false;
        }
    }

    sort(trees.rbegin(), trees.rend());

    stack <int> stk;
    for(int i = 1; i <= N; i++) {
        while(!stk.empty() and H[stk.top()] < H[i]) {
            stk.pop();
        }

        L[i] = -1;
        if(!stk.empty()) {
            L[i] = stk.top();
        }
        stk.push(i);
    }
    while(!stk.empty()) {
        stk.pop();
    }

    for(int i = N; i >= 1; i--) {
        while(!stk.empty() and H[stk.top()] < H[i]) {
            stk.pop();
        }

        R[i] = -1;
        if(!stk.empty()) {
            R[i] = stk.top();
        }
        stk.push(i);
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    A++, B++, C++, D++;
    if(subtask1 == true) {
        return C - B;
    }

    int ans = INF;
    for(int i = 1; i <= N; i++) {
        dp[i] = INF;
    }
    for(auto [h, i] : trees) {
        if(C <= i and i <= D) {
            dp[i] = 0;
        }

        if(L[i] != -1) {
            dp[i] = min(dp[i], dp[L[i]] + 1);
        }
        if(R[i] != -1) {
            dp[i] = min(dp[i], dp[R[i]] + 1);
        }

        if(A <= i and i <= B) {
            ans = min(ans, dp[i]);
        }
    }

    if(ans == INF) {
        return -1;
    }
    return ans;
}

• 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