Submission #983816

#	Time	Username	Problem	Language	Result	Execution time	Memory
983816		The_Samurai	Rainforest Jumps (APIO21_jumps)	C++17	0 / 100	4010 ms	16956 KiB

jumps

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

const int lg = 18, N = 2e5 + 5, inf = 1e9;
vector jump(lg, vector(N, N));
int n;

void init(int N, vector<int> H) {
    n = N;
    stack<int> s;
    for (int i = n - 1; i >= 0; i--) {
        while (!s.empty() and H[s.top()] < H[i]) s.pop();
        jump[0][i] = s.empty() ? n : s.top();
        s.push(i);
        if (jump[0][i] == n) continue;
        for (int j = 1; j < lg; j++) {
            jump[j][i] = jump[j - 1][jump[j - 1][i]];
            if (jump[j][i] >= n) break;
        }
    }
}

int minimum_jumps(int a, int b, int c, int d) {
    int ans = inf;
    for (int i = a; i <= b; i++) {
        int x = i, now = 0;
        for (int j = lg - 1; j >= 0; j--) {
            if (jump[j][x] >= c) continue;
            x = jump[j][x];
            now += 1 << j;
        }
        if (c <= jump[0][x] and jump[0][x] <= d) ans = min(ans, now + 1);
    }
    if (ans == inf) return -1;
    return ans;
}

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