제출 #1223483

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1223483		KALARRY	밀림 점프 (APIO21_jumps)	C++20	31 / 100	4062 ms	36468 KiB

jumps

//chockolateman

#include<bits/stdc++.h>

using namespace std;


int n,l[200005],r[200005],a[200005],up_max[200005][20],up_min[200005][20];

void init(int N, std::vector<int> H) {
    for(int i = 1 ; i <= N ; i++)
        a[i] = H[i-1];
    n = N;
    stack<int> order;
    order.push(N+1);
    for(int i = 1 ; i <= N ; i++)
    {
        while(H[i-1] > order.top())
            order.pop();
        l[a[i]] = order.top();
        order.push(a[i]);
    }
    while(!order.empty())
        order.pop();
    order.push(N+1);
    for(int i = N ; i >= 1 ; i--)
    {
        while(H[i-1] > order.top())
            order.pop();
        r[a[i]] = order.top();
        order.push(a[i]);
    }
    for(int L = 18 ; L >= 0 ; L--)
        up_max[N+1][L] = N+1;
    for(int i = 1 ; i <= N ; i++)
        up_max[i][0] = max(l[i],r[i]);
    for(int L = 1 ; L <= 18 ; L++)
        for(int i = 1 ; i <= N ; i++)
            up_max[i][L] = up_max[up_max[i][L-1]][L-1];
    for(int L = 18 ; L >= 0 ; L--)
        up_min[N+1][L] = N+1;
    for(int i = 1 ; i <= N ; i++)
        up_min[i][0] = min(l[i],r[i]);
    for(int L = 1 ; L <= 18 ; L++)
        for(int i = 1 ; i <= N ; i++)
            up_min[i][L] = up_min[up_min[i][L-1]][L-1];
}


int ans(long long v,long long targ)
{
    long long sums = (1ll<<18);
    long long ret = 0;
    for(int L = 18 ; L >= 0 ; L--)
    {
        while (up_max[v][L] <= targ)
        {
            v = up_max[v][L];
            ret += sums;
        }
        sums /= 2;
    }
        
    sums = (1ll<<18);
    for(int L = 18 ; L >= 0 ; L--)
    {
        while (up_min[v][L] <= targ)
        {
            v = up_min[v][L];
            ret += sums;
        }
        sums /= 2;
    }
    if(v != targ)
        ret = n+1;
    return ret;
}

int minimum_jumps(int A, int B, int C, int D) {
    A++;
    B++;
    C++;
    D++;
    int ret = 1e9;
    for(int i = A ; i <= B ; i++)
        for(int j = C ; j <= D ; j++)
        {
            ret = min(ret,ans(a[i],a[j]));
        }
            if(ret > n)
        ret = -1;
    return ret;
}

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