Submission #618029

#	Time	Username	Problem	Language	Result	Execution time	Memory
618029		AmirElarbi	Rainforest Jumps (APIO21_jumps)	C++14	56 / 100	4103 ms	75596 KiB

jumps

#include <bits/stdc++.h>
#define vi vector<int>
#define ve vector
#define ll long long
#define vf vector<float>
#define vll vector<pair<ll,ll>>
#define ii pair<int,int>
#define pll pair<ll,ll>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 2e9+5
#define eps 1e-7
#define eps1 1e-25
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 1e5+5
#define V 450
using namespace std;
const int MOD = 1e9;
const int nax = 4e5+5;
const int lg = 30;
int nxt[nax][lg],lst[nax][lg], mx[nax],bst[nax][lg];
vi s;
void init(int n, vi h) {
    s = h;
    stack<ii> st;
    for (int i = n-1; i >= 0; --i)
    {
        while(!st.empty() && st.top().fi <= h[i]){
            st.pop();
        }
        if(st.empty()) bst[i][0] = nxt[i][0] = i; 
        else bst[i][0] = nxt[i][0] = st.top().se, mx[i] = st.top().fi;
        st.push({h[i], i});
    }
    while(!st.empty()) st.pop();
    for (int i = 0; i < n-1; ++i)
    {
        while(!st.empty() && st.top().fi <= h[i]){
            st.pop();
        }
        if(st.empty()) lst[i][0] = i; 
        if(!st.empty()) {
            lst[i][0] = st.top().se; 
            if(mx[i] < st.top().fi) bst[i][0] = st.top().se;
        }
        st.push({h[i], i});
    }
    for (int i = 1; i < lg; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            nxt[j][i] = nxt[nxt[j][i-1]][i-1];
            bst[j][i] = bst[bst[j][i-1]][i-1];
            lst[j][i] = lst[lst[j][i-1]][i-1];
        }
    }
}

int minimum_jumps(int a, int b, int c, int d) {
    int mn = INF;
    int mxp = b+1;
    if(mxp ==c){
        if(c <= nxt[b][0] && nxt[b][0] <= d) return 1 ;
        return -1;
    }
    for (int i = lg-1; i >= 0; i--)
    {
        if(nxt[mxp][i] < c){
            mxp = nxt[mxp][i];
        }
    }
    if(nxt[mxp][0] > d) return -1;
    for (int j = a; j <= b; ++j)
    {
        int cur = j, res = 0;
        for (int i = lg-1; i >= 0; i--)
        {
            if(s[bst[cur][i]] < s[mxp]){
                cur = bst[cur][i];
                res += (1 << i);
            }
        }
        int u = lst[cur][0], v = nxt[u][0];
        if(v >= c && v <= d){
            if(u >= a && u <= b) return 1;
            else mn = min(mn,res+2);
        }
        for (int i = lg-1; i >= 0; i--)
        {
            if(nxt[cur][i] < c){
                cur = nxt[cur][i];
                res += (1 << i);
            }
        }
        if(nxt[cur][0] >= c && nxt[cur][0] <= d) mn = min(mn, res+1);
    }
    if(mn == INF) return -1;
    return mn;
}

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