제출 #954675

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
954675		Unforgettablepl	밀림 점프 (APIO21_jumps)	C++17	0 / 100	4057 ms	36504 KiB

jumps

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

#define int long long

int L[200001];
int arr[200001];
int rarr[200001];
int lift[200001][18];
int n;

void init(int32_t N, vector<int32_t> H) {
    n=N;
    for(int i=0;i<N;i++)arr[i]=H[i];
    for(int i=0;i<N;i++)rarr[arr[i]]=i;
    stack<int> q;
    for(int i=0;i<N;i++){
        while(!q.empty() and q.top()<arr[i])q.pop();
        if(!q.empty())L[arr[i]]=q.top();
        else L[arr[i]]=-1;
        q.emplace(arr[i]);
    }
    while(!q.empty())q.pop();
    for(int i=N-1;i>=0;i--){
        while(!q.empty() and q.top()<arr[i])q.pop();
        if(!q.empty())lift[arr[i]][0]=q.top();
        else lift[arr[i]][0]=-1;
        q.emplace(arr[i]);
    }
    lift[n][0]=n;
    for(int i=1;i<=N;i++)if(L[i]>lift[i][0])swap(L[i],lift[i][0]);
    for(int bit=1;bit<=17;bit++){
        for(int i=1;i<=N;i++){
            lift[i][bit] = lift[lift[i][bit-1]][bit-1];
        }
    }
}

int getans(int base,int tar){
    if(base>tar or base==-1)return INT32_MAX;
    int ans = 0;
    for(int jump=17;jump>=0;jump--){
        if(lift[base][jump]<tar) { base = lift[base][jump]; ans|=(1<<jump); }
    }
    if(L[base]==tar or lift[base][0]==tar)return ans+1;
    return ans+1+getans(L[base],tar);
}

int32_t minimum_jumps(int32_t A, int32_t B, int32_t C, int32_t D) {
    int base = arr[A];
    int tar = arr[C];
    return getans(base,tar)>=INT32_MAX ? -1 : getans(base,tar);
}

• 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