Submission #1291958

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291958		Hamed_Ghaffari	Rainforest Jumps (APIO21_jumps)	C++20	33 / 100	4099 ms	74760 KiB

jumps

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

#define maxs(a, b) (a = max(a, b))

const int MXN = 2e5+5;
const int LOG = 18;

int n, a[MXN], L[MXN], R[MXN];
int lft[LOG][MXN], rgt[LOG][MXN], nxt[LOG][MXN], mx[2][LOG][MXN];

int get_max(int l, int r) {
    for(int i=LOG-1; i>=0; i--)
        if(lft[i][r]>=l)
            r = lft[i][r];
    return a[r];
}

void init(int N, vector<int> H) {
    n = N;
    a[0] = a[n+1] = 1e9;
    for(int i=1; i<=n; i++) {
        a[i] = H[i-1];
        for(L[i]=i-1; a[L[i]]<=a[i]; L[i]=L[L[i]]);
        lft[0][i] = L[i];
        for(int j=1; j<LOG; j++)
            lft[j][i] = lft[j-1][lft[j-1][i]];
    }
    for(int i=0; i<LOG; i++) rgt[i][n+1] = n+1;
    for(int i=n; i>=1; i--) {
        for(R[i]=i+1; a[R[i]]<=a[i]; R[i]=R[R[i]]);
        rgt[0][i] = R[i];
        for(int j=1; j<LOG; j++)
            rgt[j][i] = rgt[j-1][rgt[j-1][i]];
    }
    for(int i=0; i<LOG; i++) {
        nxt[i][0] = 0;
        nxt[i][n+1] = n+1;
        mx[0][i][0] = 0;
        mx[1][i][0] = 1e9;
        mx[0][i][n+1] = n+1;
        mx[1][i][n+1] = 1e9;
    }
    for(int i=1; i<=n; i++)
        if(a[L[i]]>a[R[i]]) {
            nxt[0][i] = L[i];
            mx[0][0][i] = L[i];
            mx[1][0][i] = a[L[i]];
        }
        else {
            nxt[0][i] = R[i];
            mx[0][0][i] = R[i];
            mx[1][0][i] = a[R[i]];
        }
    for(int i=1; i<LOG; i++)
        for(int j=1; j<=n; j++)
            nxt[i][j] = nxt[i-1][nxt[i-1][j]],
            mx[0][i][j] = max(mx[0][i-1][j], mx[0][i-1][nxt[i-1][j]]),
            mx[1][i][j] = max(mx[1][i-1][j], mx[1][i-1][nxt[i-1][j]]);
}

int minimum_jumps(int A, int B, int C, int D)  {
    A++; B++; C++; D++;
    int mx2 = get_max(C, D);
    if(get_max(B, C-1)>mx2) return -1;
    int v=B;
    for(int i=LOG-1; i>=0; i--)
        if(lft[i][v]>=A && a[lft[i][v]]<mx2)
            v = lft[i][v];
    // int ans = 1;
    // for(int i=LOG-1; i>=0; i--)
    //     if(mx[0][i][v]<C && mx[1][i][v]<mx2)
    //         ans += 1<<i,
    //         v = nxt[i][v];
    // for(int i=LOG-1; i>=0; i--)
    //     if(rgt[i][v]<C)
    //         ans += 1<<i,
    //         v = rgt[i][v];
    int ans = 0;
    while(R[v]<C && a[L[v]]<mx2) {
        ans++;
        if(a[L[v]]>a[R[v]]) v = L[v];
        else v = R[v];
    }
    while(v<C) {
        ans++;
        v = R[v];
    }
    return ans;
}

• Subtask 1: 0 / 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