제출 #1196958

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1196958		NoMercy	밀림 점프 (APIO21_jumps)	C++20	0 / 100	92 ms	52760 KiB

jumps

#include "jumps.h"

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

const int lg = 20, MAXN = 2e5 + 55;
int up[lg][MAXN][2][2], N, H[MAXN];

void init(int n, vector<int> h) {
    N = n;
    H[0] = 1e9 + 7;
    for (int i = 1;i <= N;i ++) H[i] = h[i - 1];
    {
        stack<int> st;
        for (int i = 1;i <= N;i ++) {
            while (st.size() > 0 && H[st.top()] <= H[i]) st.pop();
            if (st.size() > 0) {
                up[0][i][0][0] = st.top();
                up[0][i][0][1] = 1;
            }
            st.push(i);
        } while (st.size() > 0) st.pop();

        for (int i = N;i >= 1;i --) {
            while (st.size() > 0 && H[st.top()] <= H[i]) st.pop();
            if (st.size() > 0) {
                if (up[0][i][0][0] == 0) {
                    up[0][i][0][0] = st.top();
                    up[0][i][0][1] = 1;
                } else if (H[up[0][i][0][0]] < H[st.top()]) {
                    up[0][i][1][0] = st.top();
                    up[0][i][1][1] = 1;
                } else {
                    up[0][i][1][0] = up[0][i][0][0];
                    up[0][i][0][0] = st.top();
                    up[0][i][0][1] = up[0][i][1][1] = 1;
                }
            }
            st.push(i);
        }
    }

    for (int bt = 1;bt < lg;bt ++) {
        for (int i = 0;i <= N;i ++) {
            up[bt][i][0][0] = up[bt - 1][up[bt - 1][i][0][0]][0][0];
            up[bt][i][0][1] = up[bt - 1][up[bt - 1][i][0][0]][0][1] + up[bt - 1][i][0][1];

            up[bt][i][1][0] = up[bt - 1][up[bt - 1][i][1][0]][1][0];
            up[bt][i][1][1] = up[bt - 1][up[bt - 1][i][1][0]][1][1] + up[bt - 1][i][1][0];
        }
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    B ++;
    D ++;
    int cnt = 0;
    for (int i = lg - 1;i >= 0;i --) if (H[up[i][B][1][0]] <= H[D]) {
        cnt += up[i][B][1][1];
        B = up[i][B][1][0];
    }
    for (int i = lg - 1;i >= 0;i --) if (H[up[i][B][0][0]] <= H[D]) {
        cnt += up[i][B][0][1];
        B = up[i][B][0][0];
    }

    if (B != D) {
        return -1;
    }

    return cnt;
}

• 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