제출 #963612

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
963612		socpite	밀림 점프 (APIO21_jumps)	C++14	100 / 100	786 ms	46680 KiB

jumps

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

const int maxn = 2e5+5;
const int lg = 18;

int n;

int sp_left[lg][maxn], sp_both[lg][maxn], sp_right[lg][maxn];
int l[maxn], r[maxn];

void init(int N, vector<int> H){
	n = N;
    stack<int> stk;
    for(int i = 0; i < N; i++){
        while(!stk.empty() && H[stk.top()] < H[i])stk.pop();
        if(stk.empty())l[i] = sp_left[0][i] = -1;
        else l[i] = sp_left[0][i] = stk.top();
        stk.push(i);
    }
    while(!stk.empty())stk.pop();
    for(int i = N-1; i >= 0; i--){
        while(!stk.empty() && H[stk.top()] < H[i])stk.pop();
        if(stk.empty())r[i] = sp_right[0][i] = N;
        else r[i] = sp_right[0][i] = stk.top();
        stk.push(i);
        if(l[i] == -1 && r[i] == N)sp_both[0][i] = -1;
        else if(l[i] == -1 || (r[i] != N && H[r[i]] > H[l[i]]))sp_both[0][i] = r[i];
        else sp_both[0][i] = l[i];
    }
    for(int i = 1; i < lg; i++){
        for(int j = 0; j < N; j++){
            if(sp_left[i-1][j] == -1)sp_left[i][j] = -1;
            else sp_left[i][j] = sp_left[i-1][sp_left[i-1][j]];
            if(sp_both[i-1][j] == -1)sp_both[i][j] = -1;
            else sp_both[i][j] = sp_both[i-1][sp_both[i-1][j]];
            if(sp_right[i-1][j] == N)sp_right[i][j] = N;
            else sp_right[i][j] = sp_right[i-1][sp_right[i-1][j]];
        }
    }
}

int minimum_jumps(int A, int B, int C, int D){
    if(r[B] > D)return -1;
    for(int i = lg-1; i >= 0; i--){
        if(sp_left[i][B] < A || r[sp_left[i][B]] > D)continue;
		B = sp_left[i][B];
    }
	// r[B] <= D
	int res = 0;
	for(int i = lg-1; i >= 0; i--){
		if(sp_both[i][B] == -1 || r[sp_both[i][B]] > C)continue;
		// cout << i << " " << sp_both[i][B] << endl;
		res += (1<<i);
		B = sp_both[i][B];
	}
	if(r[B] >= C)return res+1;
	if(sp_both[0][B] != -1 && r[sp_both[0][B]] <= D)return res + 2;
	for(int i = lg-1; i >= 0; i--){
		if(sp_right[i][B] == n || r[sp_right[i][B]] > C)continue;
		res += (1<<i);
		B = sp_right[i][B];
	}
	if(r[B] >= C)return res+1;
	// next move makes r[B] > C
	B = r[B];
	res++;
	if(r[B] <= D)return res+1;
	return -1;
}

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 23 / 23
• Subtask 6: 21 / 21
• Subtask 7: 19 / 19