Submission #485629

#	Time	Username	Problem	Language	Result	Execution time	Memory
485629		MOUF_MAHMALAT	Rainforest Jumps (APIO21_jumps)	C++14	0 / 100	2 ms	456 KiB

jumps

#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll oo=2e5+1;
ll n,l[19][200009],r[19][200009],u[19][200009];
stack<ll>st;
void init(int N,vector<int>H)
{
    n=N;
    l[0][oo]=r[0][oo]=oo;
    st.push(oo);
    for(ll i=0; i<n; i++)
    {
        while((!st.empty())&&H[st.top()]<H[i])
            st.pop();
        l[0][i]=st.top();
    }
    while(st.top()!=oo)
        st.pop();
    for(ll i=n-1; i>=0; i--)
    {
        while((!st.empty())&&H[st.top()]<H[i])
            st.pop();
        r[0][i]=st.top();
    }
    for(ll i=0; i<n; i++)
    {
        if(H[l[0][i]]>H[r[0][i]]&&H[l[0][i]]<oo)
            u[0][i]=l[0][i];
        else
            u[0][i]=r[0][i];
    }
    for(ll j=1; j<19; j++)
        for(ll i=0; i<n; i++)
        {
            l[j][i]=l[j-1][l[j-1][i]];
            r[j][i]=r[j-1][r[j-1][i]];
            u[j][i]=u[j-1][u[j-1][i]];
        }
}
int minimum_jumps(int A, int B, int C, int D)
{
    ll s=B,ans=0;
    for(ll i=18; i>=0; i--)
        if(l[i][s]>=A&&r[0][l[i][s]]<=D)
            s=l[i][s];
    for(ll i=18; i>=0; i--)
        if(r[0][u[i][s]]<C)
        {
            s=u[i][s];
            ans+=(1<<i);
        }
    for(ll i=18; i>=0; i--)
        if(r[i][s]<C)
        {
            s=r[i][s];
            ans+=(1<<i);
        }
    if(r[0][s]>=C&&r[0][s]<=D)
        return ans+1;
    return -1;
}

• 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