Submission #1184568

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184568		Ak_16	Rainforest Jumps (APIO21_jumps)	C++20	100 / 100	503 ms	77472 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
#define maxn 200005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;

int n, h[maxn], pre[maxn], nex[maxn];
int f[20][maxn];
int jp[20][maxn], gojo[20][maxn];
ii orz[20][maxn];

void init(int N, vector<int> H) {
    n = N;
    for (int i = 1; i <= n; i++) h[i] = H[i-1];
    h[0] = h[n+1] = INT_MAX;
    for (int i = 1; i <= n; i++) {
        int k = i-1;
        while (h[k] < h[i]) k = pre[k];
        pre[i] = k;
    }
    for (int i = n; i >= 1; i--) {
        int k = i+1;
        while (h[k] < h[i]) k = nex[k];
        nex[i] = k;
    }
    for (int i = 1; i <= n; i++) {
        jp[0][i] = pre[i];
        gojo[0][i] = nex[i];
    }
    gojo[0][n+1] = n+1;

    for (int i = 1; i <= n; i++) orz[0][i] = ii{h[i], i};
    for (int i = 1; (1<<i) <= n; i++)
        for (int j = 1; j + (1<<i) - 1 <= n; j++) orz[i][j] = max(orz[i-1][j], orz[i-1][j+(1<<(i-1))]);
    for (int i = 1; i <= n; i++) {
        if (pre[i] > 0 && nex[i] <= n) {
            f[0][i] = (h[pre[i]] > h[nex[i]] ? pre[i] : nex[i]);
            continue;
        }
        if (pre[i] > 0) {
            f[0][i] = pre[i];
            continue;
        }
        if (nex[i] <= n) {
            f[0][i] = nex[i];
            continue;
        }
        f[0][i] = n+1;
    }
    f[0][n+1] = n+1;
    for (int i = 1; i < 20; i++) for (int j = 1; j <= n+1; j++) f[i][j] = f[i-1][f[i-1][j]];
    for (int i = 1; i < 20; i++) {
        for (int j = 0; j <= n; j++) jp[i][j] = jp[i-1][jp[i-1][j]];
        for (int j = 1; j <= n+1;j++)gojo[i][j] = gojo[i-1][gojo[i-1][j]];
    }
}

ii get_max(int u, int v) {
    int k = __lg(v-u+1);
    return max(orz[k][u], orz[k][v-(1<<k)+1]);
}

int kc[maxn];
int minimum_jumps(int A, int B, int C, int D) {
    ++A; ++B; ++C; ++D;
    ii m = get_max(B, C-1), m2 = get_max(C, D);
    if (m.fi > m2.fi) return -1;
    int lo = A-1, hi = B;
    while (hi - lo > 1) {
        int mid = (lo + hi) >> 1;
        if (get_max(mid, B).fi < m2.fi) hi = mid;
        else lo = mid;
    }
    
    A = get_max(hi, B).se; 
    if (nex[A] >= C) {
        A = nex[A];
        return 1;
    }
    int ans = 0;
    for (int i = 19; i >= 0; i--){
      
    if (h[f[i][A]] <= m.fi) {
        ans += (1<<i);
        A = f[i][A];
        
    }
    }
    
    if (A != m.se) {
        if (h[f[0][A]] <= m2.fi) {
            A = f[0][A];
            ++ans;
        }
    }
    for (int i = 19; i >= 0; i--)
    if (gojo[i][A] < C) {
        ans += (1<<i);
        A = gojo[i][A];
    }
    if (A < C) {
        ++ans;
        A = nex[A];
    }
    return (C <= A and A <= D ? ans : -1);
}

• 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