Submission #738392

#	Time	Username	Problem	Language	Result	Execution time	Memory
738392		Abrar_Al_Samit	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	1442 ms	45864 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;


const int nax = 200004;
const int lg = 18;

int lef[nax][lg], rit[nax][lg], hi[nax][lg];
int a[nax];

void init(int N, vector<int> H) {
    for(int i=0; i<N; ++i) {
        a[i] = H[i];
    }
    stack<int>st;
    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(!st.empty() && H[st.top()]<a[i]) {
            rit[st.top()][0] = i;
            st.pop();
        }
        st.push(i);
    }

    while(!st.empty()) st.pop();
    for(int i=N-1; i>=0; --i) {
        while(!st.empty() && H[st.top()]<a[i]) {
            lef[st.top()][0] = i;
            st.pop();
        }
        st.push(i);
    }

    for(int i=0; i<N; ++i) {
        hi[i][0] = (H[lef[i][0]]>H[rit[i][0]]) ? lef[i][0] : rit[i][0];
    }

    for(int j=1; j<lg; ++j) {
        for(int i=0; i<N; ++i) {
            lef[i][j] = lef[lef[i][j-1]][j-1];
            rit[i][j] = rit[rit[i][j-1]][j-1];
            hi[i][j] = hi[hi[i][j-1]][j-1];
        }
    }
}

int getMAX(int C, int D) {
    int at = C;
    for(int j=lg-1; j>=0; --j) {
        if(rit[at][j]<=D) {
            at = rit[at][j];
        }
    }
    return a[at];
}
int getStart(int A, int B, int mx) {
    int at = B;
    for(int j=lg-1; j>=0; --j) {
        if(lef[at][j]>=A && a[lef[at][j]]<mx) {
            at = lef[at][j];
        }
    }
    return at;
}
int finish(int at, int C, int D) {
    int ret = 0;
    for(int j=lg-1; j>=0; --j) {
        if(rit[at][j]<C) {
            ret |= 1<<j;
            at = rit[at][j];
        }
    }
    ++ret;
    at = rit[at][0];
    if(at>=C && at<=D) return ret;
    return -1;
}
int minimum_jumps(int A, int B, int C, int D) {
    int mx = getMAX(C, D);
    int l = getStart(A, B, mx);

    if(a[l]>mx) return -1;

    int ans = 0;
    int cur = l;
    for(int j=lg-1; j>=0; --j) {
        int at = hi[cur][j];
        if(a[at]>=mx) continue;
        if(rit[at][0]>=C) continue;

        cur = at;
        ans |= 1<<j;
    }

    int np = finish(cur, C, D);
    if(a[hi[cur][0]]<=mx) {
        int curnp = finish(hi[cur][0], C, D);
        if(curnp!=-1) {
            np = min(np, curnp+1);
        }
    }
    if(np==-1) return -1;
    ans += np;
    return ans;
}

• 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