Submission #569114

#	Time	Username	Problem	Language	Result	Execution time	Memory
569114		niloyroot	Rainforest Jumps (APIO21_jumps)	C++14	37 / 100	4080 ms	15248 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
using ll = int; //long long;
using vi = vector<ll>;
using pl = pair<ll,ll>;
#define pb push_back
#define form(m,it) for(auto it=m.begin(); it!=m.end(); it++)
#define forp(i,a,b) for(ll i=a; i<=b; i++)
#define forn(i,a,b) for(ll i=a; i>=b; i--)
#define newl '\n'
#define ff first
#define ss second
const ll mod = 1e9 + 7;
ll n;
bool g=1;
ll h[200005];
vi adj[200005];

void init(ll N, vi he){
    n = N;
    forp(i,1,n){
        h[i] = he[i-1];
    }

    stack<pl> st;
    st.push({h[1],1});

    forp(i,2,n){
        while(!st.empty()&&st.top().ff<=h[i]){
            st.pop();
        }
        if(st.size()>=1 && st.top().ff>h[i]){
            adj[i].pb(st.top().ss);
        }
        st.push({h[i],i});
    }

    while(!st.empty()){st.pop();}
    st.push({h[n],n});

    forn(i,n-1,1){
        while(!st.empty()&&st.top().ff<=h[i]){
            st.pop();
        }
        if(st.size()>=1 && st.top().ff>h[i]){
            adj[i].pb(st.top().ss);
        }
        st.push({h[i],i});
    }

    forp(i,1,n){
        if(h[i]!=i)g=0;
    }
}

int minimum_jumps(ll a, ll b, ll c, ll d){
    if(g){
        return c-b;
    }

    queue<pl> q;
    bool vis[n+1] = {0};
    a++; b++; c++; d++;
    forp(i,a,b){
        q.push({i,0});
        vis[i]=1;
    }

    while(!q.empty()){
        ll nd = q.front().ff; ll dis = q.front().ss; q.pop();
        if(nd<=d && c<=nd){
            return dis;
        }
        for(auto u:adj[nd]){
            if(!vis[u]){
                vis[u]=1;
                q.push({u,dis+1});
            }
        }
    }

    return -1;
}

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