Submission #870608

#	Time	Username	Problem	Language	Result	Execution time	Memory
870608		LOLOLO	Rainforest Jumps (APIO21_jumps)	C++14	100 / 100	820 ms	82116 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const ll N = 2e5 + 100;
int h[N], sp[N][20], low[N][20], high[N][20], n, l[N][20], r[N][20];
 
void init(int _n, vector <int> _h) {
    n = _n;
    for (int i = 1; i <= n; i++) {
        h[i] = _h[i - 1];
        sp[i][0] = high[i][0] = low[i][0] = r[i][0] = i;
    }
 
    r[n + 1][0] = low[n + 1][0] = high[n + 1][0] = n + 1;
    h[0] = h[n + 1] = 1e9;
 
    stack <int> st;
    for (int i = 0; i <= n; i++) {
        while (sz(st) && h[i] > h[st.top()]) {
            st.pop();
        }
 
        if (sz(st)) {
            l[i][0] = high[i][0] = low[i][0] = st.top();
        }
 
        st.push(i);
    }
 
    while (sz(st))
        st.pop();
 
    for (int i = n + 1; i >= 1; i--) {
        while (sz(st) && h[i] > h[st.top()]) {
            st.pop();
        }
 
        if (sz(st)) {
            if (h[high[i][0]] <= h[st.top()]) {
                high[i][0] = st.top();
            } else {
                low[i][0] = st.top();
            }
 
            r[i][0] = st.top();
        }
 
        st.push(i);
    }
 
    for (int i = 1; i < 20; i++) {
        for (int j = 0; j <= n + 1; j++) {
            high[j][i] = high[high[j][i - 1]][i - 1];
            low[j][i] = low[low[j][i - 1]][i - 1];
            l[j][i] = l[l[j][i - 1]][i - 1];
            r[j][i] = r[r[j][i - 1]][i - 1];
        }
    }
 
    for (int i = n; i >= 1; i--) {
        for (int j = 1; (1 << j) + i <= n + 1; j++) {
            int L = sp[i][j - 1], R = sp[i + (1 << (j - 1))][j - 1];
            sp[i][j] = h[L] > h[R] ? L : R;
        }
    }
}
 
int max_index(int l, int r) {
    int k = log2(r - l + 1);
    int L = sp[l][k], R = sp[r - (1 << k) + 1][k];
    return h[L] > h[R] ? L : R;
}
 
int minimum_jumps(int a, int b, int c, int d) {
    a++, b++, c++, d++;
    int p = max_index(c, d);
 
    if (b == c - 1) {
        return h[b] < h[p] ? 1 : -1;
    }
 
    int mid = max_index(b + 1, c - 1);
    if (h[mid] > h[p])
        return -1;
 
    int st = b, cnt = 0;
 
    for (int i = 19; i >= 0; i--) {
        if (l[st][i] >= a && h[l[st][i]] < h[mid]) {
            st = l[st][i];
        }
    }

    if (l[st][0] >= a && r[l[st][0]][0] <= d)
        return 1;

    int v = 1e9;
    for (int i = 19; i >= 0; i--) {
        if (h[high[st][i]] <= h[mid]) {
            cnt += (1 << i);
            st = high[st][i];
        }
    }

    if (high[st][0] >= 1 && r[high[st][0]][0] <= d)
        v = cnt + 2;
 
    for (int i = 19; i >= 0; i--) {
        if (h[low[st][i]] <= h[mid]) {
            cnt += (1 << i);
            st = low[st][i];
        }
    }
 
    if (r[st][0] <= d)
        return min(cnt + 1, v);

    if (v < 1e9)
        return v;

    return -1;
}

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 23 / 23
• Subtask 6: 21 / 21
• Subtask 7: 19 / 19