Submission #1099474

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099474		gyg	Rainforest Jumps (APIO21_jumps)	C++17	0 / 100	170 ms	64548 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
#define arr array
#define vct vector 
const lint N = 2e5 + 5;

lint n;
arr<lint, N> h;

arr<lint, N> l, r;
arr<arr<lint, 22>, N> jmp1, jmp2;
void prcmp() {
    stack<lint> ord;
    for (lint i = 1; i <= n; i++) {
        while (ord.size() && h[ord.top()] < h[i]) ord.pop();
        if (ord.size()) l[i] = ord.top();
        ord.push(i);
    }
    while (ord.size()) ord.pop();
    for (lint i = n; i >= 1; i--) {
        while (ord.size() && h[ord.top()] < h[i]) ord.pop();
        if (ord.size()) r[i] = ord.top();
        ord.push(i);
    }

    for (lint u = 1; u <= n; u++) {
        jmp1[u][0] = (h[l[u]] > h[r[u]]) ? l[u] : r[u];
        jmp2[u][0] = r[u];
    }
    for (lint i = 1; i <= 20; i++) 
        for (lint u = 1; u <= n; u++)
            jmp1[u][i] = jmp1[jmp1[u][i - 1]][i - 1], jmp2[u][i] = jmp2[jmp2[u][i - 1]][i - 1];    
    
    // for (lint i = 1; i <= n; i++) cout << l[i] << " " << r[i] << endl;
    // for (lint i = 1; i <= n; i++) cout << jmp1[i][0] << endl;
}

void init(int _n, vector<int> _h) {
    n = _n;
    for (lint i = 1; i <= n; i++) h[i] = _h[i - 1];
    prcmp();
}

vct<lint> lft1(lint u, lint x) {
    lint dst = 0;
    for (lint i = 20; i >= 0; i--)
        if (jmp1[u][i] != 0 && h[jmp2[u][i]] <= x)
            u = jmp1[u][i], dst += (1 << i);
    return {u, dst};
}
vct<lint> lft2(lint u, lint x) {
    if (h[u] >= x) return {u, 0};
    lint dst = 0;
    for (lint i = 20; i >= 0; i--)
        if (jmp2[u][i] != 0 && h[jmp2[u][i]] < x)
            u = jmp2[u][i], dst += (1 << i);
    u = jmp2[u][0], dst++;
    return {u, dst};
}

int minimum_jumps(int _u1, int _u2, int _v1, int _v2) {
    lint u = _u1 + 1, v = _v1 + 1;
    if (h[u] > h[v]) return -1;
    lint w = lft1(u, h[v])[0], dst1 = lft1(u, h[v])[1];
    lint x = lft2(w, h[v])[0], dst2 = lft2(w, h[v])[1];
    if (x == 0 || h[x] > h[v]) return -1;
    return dst1 + dst2;
}

• 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