Submission #1099482

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099482		gyg	Rainforest Jumps (APIO21_jumps)	C++17	0 / 100	61 ms	64236 KiB

jumps

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

int n;
arr<int, N> h;

arr<int, N> l, r;
arr<arr<int, 22>, N> jmp1, jmp2;
void prcmp() {
    stack<int> ord;
    for (int 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 (int 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 (int u = 1; u <= n; u++) {
        jmp1[u][0] = (h[l[u]] > h[r[u]]) ? l[u] : r[u];
        jmp2[u][0] = r[u];
    }
    for (int i = 1; i <= 20; i++) 
        for (int 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 (int i = 1; i <= n; i++) cout << l[i] << " " << r[i] << endl;
    // for (int i = 1; i <= n; i++) cout << jmp1[i][0] << endl;
}

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

vct<int> lft1(int u, int x) {
    int dst = 0;
    for (int 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<int> lft2(int u, int x) {
    if (h[u] >= x) return {u, 0};
    int dst = 0;
    for (int 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) {
    assert(_u1 == _u2 && _v1 == _v2);
    int u = _u1 + 1, v = _v1 + 1;
    if (h[u] > h[v]) return -1;
    int w = lft1(u, h[v])[0], dst1 = lft1(u, h[v])[1];
    assert(h[w] <= h[v]);
    int x = lft2(w, h[v])[0], dst2 = lft2(w, h[v])[1];
    // assert(x == 0 || h[x] >= h[v]);
    if (x == 0 || h[x] > h[v]) return -1;
    assert(x == v);
    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