Submission #1061646

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061646		alexdd	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	838 ms	49784 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> H;
int unde[200005];
const int INF = 1e9;
int tole[200005],tori[200005],parent[200005];
int anc[200005][18],ancri[200005][18];
int rmq[200005][18];
int p2[200005];
void init(int N, std::vector<int> copH)
{
    H=copH;
    deque<int> dq;
    for(int i=0;i<N;i++)
    {
        unde[H[i]]=i;
        rmq[i][0]=H[i];
        while(!dq.empty() && H[dq.back()] < H[i])
            dq.pop_back();
        if(dq.empty())
            tole[i]=-1;
        else
            tole[i]=dq.back();
        dq.push_back(i);
    }
    dq.clear();
    for(int i=N-1;i>=0;i--)
    {
        while(!dq.empty() && H[dq.back()] < H[i])
            dq.pop_back();
        if(dq.empty())
            tori[i]=N;
        else
            tori[i]=dq.back();
        dq.push_back(i);
        if(tole[i]>-1 && H[tole[i]] > H[tori[i]])
            parent[i] = tole[i];
        else
            parent[i] = tori[i];
    }
    for(int p=1;p<18;p++)
        for(int i=0;i+(1<<p)-1<N;i++)
            rmq[i][p] = max(rmq[i][p-1], rmq[i+(1<<(p-1))][p-1]);
    for(int i=1;i<=N;i++)
    {
        p2[i]=p2[i-1];
        while((1<<(p2[i]+1))<=i)
            p2[i]++;
    }
    tori[N]=N;
    for(int i=0;i<N;i++)
    {
        anc[i][0] = parent[i];
        ancri[i][0] = tori[i];
    }
    anc[N][0]=ancri[N][0]=N;
    for(int p=1;p<18;p++)
    {
        for(int i=0;i<=N;i++)
        {
            anc[i][p] = anc[anc[i][p-1]][p-1];
            ancri[i][p] = ancri[ancri[i][p-1]][p-1];
        }
    }
}
int getmax(int le, int ri)
{
    if(le>ri)
        return 0;
    int p = p2[ri-le+1];
    return max(rmq[le][p], rmq[ri-(1<<p)+1][p]);
}
int getdist(int cur, int le, int ri)
{
    int pasi=0,mxm=getmax(le,ri);
    for(int p=17;p>=0;p--)
    {
        if(tori[anc[cur][p]] < le && tole[cur]!=-1 && H[tole[cur]]<=mxm)
        {
            cur = anc[cur][p];
            pasi += (1<<p);
        }
    }
    while(1)
    {
        if(tole[cur]==-1 || H[tole[cur]] > mxm)
            break;
        if(tori[cur]>=le && tori[cur]<=ri)
            return pasi+1;
        cur = parent[cur];
        pasi++;
    }
    ///acum putem merge doar spre dreapta
    for(int p=17;p>=0;p--)
    {
        if(ancri[cur][p] < le)
        {
            cur = ancri[cur][p];
            pasi += (1<<p);
        }
    }
    pasi++;
    return pasi;
}
int minimum_jumps(int A, int B, int C, int D)
{
    if(getmax(B+1,C-1) > getmax(C,D))
        return -1;
    if(H[B] > getmax(C,D))
        return -1;

    int st=A,dr=B,primu=-1;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(getmax(mij,B) < getmax(C,D))
        {
            primu=unde[getmax(mij,B)];
            dr=mij-1;
        }
        else
        {
            st=mij+1;
        }
    }
    if(primu==-1)
        return -1;
    else
        return getdist(primu,C,D);
}

• 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