Submission #1060249

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060249		alexdd	Rainforest Jumps (APIO21_jumps)	C++17	0 / 100	4037 ms	17496 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int parent[200005];
int anc[200005][18];
void init(int N, std::vector<int> H)
{
    deque<int> dq;
    for(int i=N-1;i>=0;i--)
    {
        while(!dq.empty() && H[dq.back()] < H[i])
            dq.pop_back();
        if(dq.empty())
            parent[i]=N;
        else
            parent[i]=dq.back();
        dq.push_back(i);
    }
    parent[N]=N;
    for(int i=0;i<=N;i++)
        anc[i][0]=parent[i];
    for(int p=1;p<18;p++)
        for(int i=0;i<=N;i++)
            anc[i][p] = anc[anc[i][p-1]][p-1];
}
int getdist(int cur, int le, int ri)
{
    int pasi=0;
    for(int p=17;p>=0;p--)
    {
        if(anc[cur][p]<le)
        {
            pasi += (1<<p);
            cur = anc[cur][p];
        }
    }
    pasi++;
    cur = anc[cur][0];
    if(cur>ri)
        return INF;
    return pasi;
}
int minimum_jumps(int A, int B, int C, int D)
{
    int mnm=INF;
    for(int i=A;i<=B;i++)
        mnm = min(mnm, getdist(i,C,D));
    if(mnm==INF)
        return -1;
    else
        return mnm;
}

• 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