Submission #738804

#	Time	Username	Problem	Language	Result	Execution time	Memory
738804		Kenjikrab	Rainforest Jumps (APIO21_jumps)	C++14	100 / 100	3108 ms	45856 KiB

jumps

#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;
int const n_max=2e5+10;
int const h_max=18;
int rit[n_max][h_max],lef[n_max][h_max],hi[n_max][h_max];
int n;
vector<int> a;

void init(int N, vector<int> H)
{
    n=N;
    a=H;
    stack<int> stk;
    for(int i=0;i<n;i++)lef[i][0]=rit[i][0]=hi[i][0]=i;
    for(int i=0;i<n;i++)
    {
        while(!stk.empty()&&a[stk.top()]<a[i]) stk.pop();
        if(stk.empty()) lef[i][0]=i;
        else lef[i][0]=stk.top();
        stk.push(i);
    }
    while(!stk.empty())stk.pop();
    for(int i=n-1;i>=0;i--)
    {
        while(!stk.empty()&&a[stk.top()]<a[i]) stk.pop();
        if(stk.empty()) rit[i][0]=i;
        else rit[i][0]=stk.top();
        stk.push(i);
    }
    for(int i=0;i<n;i++)
    {
        hi[i][0]=(a[lef[i][0]]>a[rit[i][0]])? lef[i][0]:rit[i][0];
    }
    for(int i=1;i<h_max;i++)
    {
        for(int j=0;j<n;j++)
        {
            lef[j][i]=lef[lef[j][i-1]][i-1];
            rit[j][i]=rit[rit[j][i-1]][i-1];
            hi[j][i]=hi[hi[j][i-1]][i-1];
        }
    }
}

int find_mx(int C,int D)
{
    int cur=D;
    for(int i=h_max-1;i>=0;i--)
    {
        if(lef[cur][i]>=C) cur=lef[cur][i];
    }
    return a[cur];
}

int find_st(int A,int B,int mx)
{
    int cur=-1;
    for(int i=B;i>=A;i--)
    {
        if(a[i]<mx)
        {
            cur=i;
            break;
        }
    }
    if(cur==-1)return -1;
    for(int i=h_max-1;i>=0;i--)
    {
        if(lef[cur][i]>=A&&a[lef[cur][i]]<mx) cur=lef[cur][i];
    }
    return cur;
}
int find_dis(int cur,int C,int D)
{
    int ret=0;
    for(int i=h_max-1;i>=0;i--)
    {
        if(rit[cur][i]>=C)continue;
        cur=rit[cur][i];
        ret+=1<<i;
    }
    ret++;
    cur=rit[cur][0];
    if(C<=cur&&cur<=D)return ret;
    return -1;
}
int minimum_jumps(int A, int B, int C, int D)
{
    int mx=find_mx(C,D);
    int st=find_st(A,B,mx);
    if(st==-1||a[st]>mx)return -1;
    int ans=0;
    int cur=st;
    for(int i=h_max-1;i>=0;i--)
    {
        if(a[hi[cur][i]]>=mx)continue;
        if(rit[hi[cur][i]][0]>=C)continue;
        cur=hi[cur][i];
        ans+=1<<i;
    }
    int add=find_dis(cur,C,D);
    if(a[hi[cur][0]]<=mx)
    {
        int nadd=find_dis(hi[cur][0],C,D);
        if(nadd!=-1)add=min(add,nadd+1);
    }
    if(add==-1)return -1;
    return ans+add;
}

• 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