Submission #980525

#	Time	Username	Problem	Language	Result	Execution time	Memory
980525		vjudge1	Rainforest Jumps (APIO21_jumps)	C++17	0 / 100	4009 ms	53068 KiB

jumps

#include "jumps.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 200200;

int n;
int A[N];
int B[N];
int a[N];
int t[N][20];
int t2[N][20];
int L[N];
int f[N][20];

int comb_t(int i, int j) {
    return a[i] > a[j] ? i : j;
}

int comb_f(int i, int j) {
    return a[i] > a[j] ? i : j;
}

int get_f(int l, int r) {
    int g = L[r - l + 1];
    return comb_f(f[l][g], f[r - (1 << g) + 1][g]);
}

void init(int N_, std::vector<int> H) {
    for (int i = 2; i < N; i++) {
        L[i] = L[i / 2] + 1;
    }
    n = N_;

    vector<int> v;
    for (int i = 0; i < n; i++) {
        a[i] = H[i];

        while (!v.empty() && H[i] > H[v.back()]) {
            v.pop_back();
        }
        if (v.empty()) {
            A[i] = -1;
        } else {
            A[i] = v.back();
        }
        v.push_back(i);
    }
    v.clear();
    B[n] = n;
    for (int i = n - 1; i >= 0; i--) {
        while (!v.empty() && H[i] > H[v.back()]) {
            v.pop_back();
        }
        if (v.empty()) {
            B[i] = n;
        } else {
            B[i] = v.back();
        }
        v.push_back(i);
    }

    t[n][0] = n;
    t2[n][0] = n;
    for (int i = 0; i < n; i++) {
        if (A[i] != -1 || B[i] == n) {
            t[i][0] = n;
        } else {
            t[i][0] = comb_t(A[i], B[i]);
        }
        f[i][0] = i;
        t2[i][0] = B[i];
    }
    for (int i = 1; i < 20; i++) {
        for (int j = 0; j <= n; j++) {
            t[j][i] = t[t[j][i - 1]][i - 1];
            t2[j][i] = t2[t2[j][i - 1]][i - 1];

            if (j + (1 << i) - 1 < n) {
                f[j][i] = comb_f(f[j][i - 1], f[j + (1 << i - 1)][i - 1]);
            }
        }
    }
}

int get_from(int x, int C, int D) {
    int tot = 0;
    for (int i = 19; i >= 0; i--) {
        if (::B[t[x][i]] < C) {
            x = t[x][i];
            tot += (1 << i);
        }
    }

    int res = n + 1;

    for (int it = 0; it < 2; it++) {
        if (x > D) {
            continue;
        }
        int cur = 0, y = x;
        for (int i = 19; i >= 0; i--) {
            if (t2[y][i] < C) {
                y = t2[y][i];
                cur += (1 << i);
            }
        }
        if (t2[y][0] <= D) {
            res = min(res, tot + cur + 1);
        }

        x = t[x][0];
        tot += 1;
    }


    return res;
}

int minimum_jumps(int A, int B, int C, int D) {
    int res = n + 1;
    for (int i = A; i <= B; i++) {
        res = min(res, get_from(i, C, D));
    }

    if (res == n + 1) {
        return -1;
    }
    return res;
}

Compilation message (stderr)

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:82:61: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   82 |                 f[j][i] = comb_f(f[j][i - 1], f[j + (1 << i - 1)][i - 1]);
      |                                                           ~~^~~
jumps.cpp:19:15: warning: array subscript -1 is below array bounds of 'int [200200]' [-Warray-bounds]
   19 |     return a[i] > a[j] ? i : j;
      |            ~~~^

• 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