Submission #1193994

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193994		qilby	Rainforest Jumps (APIO21_jumps)	C++20	4 / 100	408 ms	49024 KiB

jumps

#include "jumps.h"

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 200009, L = 18;

int n, lg[N], h[N], o[N][L], mx[N][L], t[N][L], p[N], lft[N], rgt[N];

int get_max(int l, int r) {
    int d = lg[r - l + 1];
    return max(mx[l][d], mx[r - (1 << d) + 1][d]);
}

void init(int n_, vector < int > h_) {
    n = n_;
    for (int i = 1; i <= n; i++) h[i] = h_[i - 1];

    for (int i = 1; i <= n; i++) {
        p[h[i]] = i;
        mx[i][0] = h[i];
        if (i > 1) lg[i] = lg[i >> 1] + 1;
    }

    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
    }

    vector < int > v;

    for (int i = 1; i <= n; i++) {
        while (!v.empty() && h[v.back()] <= h[i]) v.pop_back();
        if (v.empty()) lft[i] = 1; else lft[i] = v.back();
        v.push_back(i);
    }

    v.clear();

    for (int i = n; i >= 1; i--) {
        while (!v.empty() && h[v.back()] <= h[i]) v.pop_back();
        if (v.empty()) rgt[i] = n; else rgt[i] = v.back();
        v.push_back(i);
    }

    for (int i = 1; i <= n; i++) {
        o[i][0] = (h[lft[i]] > h[rgt[i]] ? lft[i] : rgt[i]);
        t[i][0] = rgt[i];
    }

    for (int j = 1; j < L; j++) {
        for (int i = 1; i <= n; i++) {
            o[i][j] = o[o[i][j - 1]][j - 1];
            t[i][j] = t[t[i][j - 1]][j - 1];
        }
    }
}

int minimum_jumps(int l, int r, int lg, int rg) {
    l++, r++, lg++, rg++;

    int i = lft[lg];
    if (h[i] <= h[lg]) i--;

    if (i >= r) return -1;

    int j = max(i + 1, l);
    int x = get_max(j, r);
    j = p[x];

    int res = 0;

    for (int l = L - 1; l >= 0; l--) if (h[o[j][l]] < h[lg]) j = o[j][l], res += (1 << l);
    for (int l = L - 1; l >= 0; l--) if (t[j][l] < lg) j = t[j][l], res += (1 << l);

    return res + 1;
}

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