Submission #485943

#	Time	Username	Problem	Language	Result	Execution time	Memory
485943		MOUF_MAHMALAT	Rainforest Jumps (APIO21_jumps)	C++14	48 / 100	1094 ms	44964 KiB

jumps

#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
stack<ll>st;
ll n,l[18][200009],r[18][200009];
ll u[18][200009];
void init(int N, vector<int>h)
{
    n=N;
    for(ll i=0; i<n; i++)
    {
        while(!st.empty()&&h[st.top()]<h[i])
            st.pop();
        if(st.empty())
            l[0][i]=-1;
        else
            l[0][i]=st.top();
        st.push(i);
    }
    while(!st.empty())
        st.pop();
    for(ll i=n-1; i>=0; i--)
    {
        while(!st.empty()&&h[st.top()]<h[i])
            st.pop();
        if(st.empty())
            r[0][i]=-1;
        else
            r[0][i]=st.top();
        st.push(i);
    }
    for(ll i=0; i<n; i++)
    {
        if(l[0][i]==-1)
            u[0][i]=r[0][i];
        else if(r[0][i]==-1)
            u[0][i]=l[0][i];
        else if(h[l[0][i]]<h[r[0][i]])
            u[0][i]=r[0][i];
        else
            u[0][i]=l[0][i];
    }
    for(ll i=1; i<18; i++)
        for(ll j=0; j<n; j++)
        {
            if(l[i-1][j]!=-1)
                l[i][j]=l[i-1][l[i-1][j]];
            else
                l[i][j]=-1;
            if(r[i-1][j]!=-1)
                r[i][j]=r[i-1][r[i-1][j]];
            else
                r[i][j]=-1;
            if(u[i-1][j]!=-1)
                u[i][j]=u[i-1][u[i-1][j]];
            else
                u[i][j]=-1;
        }
}
int minimum_jumps(ll a,ll b,ll c,ll d)
{
    ll s=b,ans=0;
    for(ll i=17; i>=0; i--)
        if(l[i][s]>=a&&r[0][l[i][s]]!=-1&&r[0][l[i][s]]<=d)
            s=l[i][s];
    for(ll i=17; i>=0; i--)
        if(u[i][s]!=-1&&u[i][s]<c&&r[0][u[i][s]]!=-1&&r[0][u[i][s]]<=d)
            s=u[i][s],ans+=(1<<i);
    for(ll i=17; i>=0; i--)
        if(r[i][s]!=-1&&r[i][s]<c)
            s=r[i][s],ans+=(1<<i);
    if(r[0][s]>d||r[0][s]==-1)
        return -1;
    return ans+1;
}

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