Submission #1071217

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071217		stdfloat	Rainforest Jumps (APIO21_jumps)	C++17	0 / 100	1 ms	344 KiB

jumps

#include <bits/stdc++.h>
#include "jumps.h"
// #include "stub.cpp"
using namespace std;

vector<int> h, lg;

vector<vector<int>> sp, spl, spr, spmx;

int fmx(int l, int r) {
    int x = lg[r - l + 1];
    return max(spmx[l][x], spmx[r - (1 << x) + 1][x]);
}

void init(int n, vector<int> H) {
    h = H;

    lg.assign(n + 1, 0);
    for (int i = 2; i <= n; i++) {
        lg[i] = lg[i >> 1] + 1;
    }

    spmx.assign(n, vector<int>(20));
    for (int i = 0; i < n; i++) {
        spmx[i][0] = h[i];
    }

    stack<int> s;
    spl.assign(n, vector<int>(20, -1));
    for (int i = 0; i < n; i++) {
        while (!s.empty() && h[s.top()] < h[i]) s.pop();

        spl[i][0] = (s.empty() ? -1 : s.top());
        s.push(i);
    }

    while (!s.empty()) s.pop();
    
    sp = spr = spl;
    for (int i = n - 1; i >= 0; i--) {
        while (!s.empty() && h[i] > h[s.top()]) s.pop();

        if (s.empty()) sp[i][0] = spl[i][0];
        else {
            spr[i][0] = s.top();
            sp[i][0] = (spl[i][0] == -1 || h[spl[i][0]] < h[spr[i][0]] ? spr[i][0] : spl[i][0]);
        }
    
        s.push(i);
    }

    for (int i = 1; i < 20; i++) {
        for (int j = 0; j < n; j++) {
            if (sp[j][i - 1] != -1) sp[j][i] = sp[sp[j][i - 1]][i - 1];
            if (spl[j][i - 1] != -1) spl[j][i] = spl[spl[j][i - 1]][i - 1];
            if (spr[j][i - 1] != -1) spr[j][i] = spr[spr[j][i - 1]][i - 1];
            if (j + (1 << i) <= n) spmx[j][i] = max(spmx[j][i - 1], spmx[j + (1 << (i - 1))][i - 1]);
        }
    }
}

int minimum_jumps(int a, int b, int c, int d) {
    int T = fmx(b + 1, c - 1);

    for (int i = 19; i >= 0; i--) {
        if (a <= spl[b][i] && h[spl[b][i]] < T) b = spl[b][i];
    }
    
    int cnt = 0;
    for (int i = 19; i >= 0; i--) {
        if (sp[b][i] != -1 && h[sp[b][i]] <= T) {
            cnt += (1 << i);
            b = sp[b][i];
        }
    }

    for (int i = 19; i >= 0; i--) {
        if (spr[b][i] != -1 && h[spr[b][i]] <= T) {
            cnt += (1 << i);
            b = spr[b][i];
        }
    }

    return (c <= spr[b][0] && spr[b][0] <= d ? cnt + 1 : -1);
}

• 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