Submission #691601

#	Time	Username	Problem	Language	Result	Execution time	Memory
691601		Dan4Life	Rainforest Jumps (APIO21_jumps)	C++17	48 / 100	1204 ms	61092 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int maxn = (int)2e5+10;
const int maxlg = 24;
const int INF = (int)1e9;

stack<pair<int,int>> S;
int n, pr[maxn], nx[maxn];
int l[maxlg][maxn], r[maxlg][maxn], hi[maxlg][maxn];

void calc(int jmp[][maxn]){
    for(int i = 1; i < maxlg; i++)
        for(int j = 1; j <= n; j++)
            jmp[i][j] = jmp[i-1][jmp[i-1][j]];
}

void init(int N, vector<int> a) {
    n = N; a.insert(a.begin(),-1);
    for(int i = 1; i <= n; i++){
        while(!S.empty() and S.top().fi<a[i]) S.pop();
        if(!S.empty()) pr[i] = S.top().se;
        S.push({a[i],i});
    }
    while(!S.empty()) S.pop();
    for(int i = n; i>=1; i--){
        while(!S.empty() and S.top().fi<a[i]) S.pop();
        if(!S.empty()) nx[i] = S.top().se;
        S.push({a[i],i});
    }
    for(int i = 1; i <= n; i++)
        l[0][i]=pr[i], r[0][i]=nx[i],
        hi[0][i] = (a[pr[i]]<a[nx[i]]?nx[i]:pr[i]);
    calc(l), calc(r), calc(hi);
}

int get_path(int *x, int y, int z, int jmp[][maxn], int rx=1, int tot=0){
    for(int i = maxlg-1; i >= 0; i--)
        if(jmp[i][*x]>=rx and jmp[i][*x]<y)
            if(nx[jmp[i][*x]] and nx[jmp[i][*x]]<=z)
                *x = jmp[i][*x], tot+=(1<<i);
    return tot;
}

int minimum_jumps(int A, int B, int C, int D) {
    A++,B++,C++,D++;
    int x = B;
    get_path(&x,C,D,l,A);
    int num1 = get_path(&x,C,D,hi);
    int num2 = get_path(&x,C,D,r);
    return ((nx[x]>=C and nx[x]<=D)?num1+num2+1:-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