Submission #1152818

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152818		Sharky	Rainforest Jumps (APIO21_jumps)	C++20	4 / 100	476 ms	48216 KiB

jumps

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

const int N = 2e5 + 10;
const int LG = 18;
int n, sp[N][LG], h[N], pos[N], las[N], nex[N], nxt[N][LG], nxt2[N][LG], lg[N];

int query(int x, int y) {
    int j = lg[y - x + 1];
    return max(sp[x][j], sp[y - (1 << j) + 1][j]);
}

void init(int _n, std::vector<int> _h) {
    n = _n;
    for (int i = 0; i < _n; i++) {
        h[i + 1] = _h[i];
        sp[i + 1][0] = h[i + 1];
    }
    lg[1] = 0;
    for (int i = 2; i <= n; i++) lg[i] = lg[i/2] + 1;
    for (int i = 1; i <= n; i++) pos[h[i]] = i;
    for (int i = 1; i < LG; i++) {
        for (int j = 1; j + (1 << i) - 1 <= n; j++) {
            sp[j][i] = max(sp[j][i - 1], sp[j + (1 << (i - 1))][i - 1]);
        }
    }
    stack<int> st;
    for (int i = 1; i <= n; i++) {
        while (!st.empty() && h[st.top()] < h[i]) st.pop();
        if (!st.empty()) las[i] = h[st.top()];
        st.push(i);
    }
    while (!st.empty()) st.pop();
    for (int i = n; i >= 1; i--) {
        while (!st.empty() && h[st.top()] < h[i]) st.pop();
        if (!st.empty()) nex[i] = h[st.top()];
        st.push(i);
    }
    for (int i = 1; i <= n; i++) {
        nxt[h[i]][0] = max(las[i], nex[i]);
        // cout << "nxt: " << i << " " << nxt[i][0] << '\n';
        if (!nxt[h[i]][0]) nxt[h[i]][0] = n + 1;
        if (!las[i] && !nex[i]) nxt2[h[i]][0] = n + 1;
        else if (!las[i]) nxt2[h[i]][0] = nex[i];
        else if (!nex[i]) nxt2[h[i]][0] = las[i];
        else nxt2[h[i]][0] = min(las[i], nex[i]);
    }
    nxt[n + 1][0] = nxt2[n + 1][0] = n + 1;
    for (int j = 1; j < LG; j++) {
        for (int i = 1; i <= n + 1; i++) {
            nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
            nxt2[i][j] = nxt2[nxt2[i][j - 1]][j - 1];
        }
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    A++, B++, C++, D++;
    int right_max = query(C, D);
    int lo = A, hi = B;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (query(mid, C-1) <= right_max) hi = mid;
        else lo = mid + 1;
    }
    if (query(lo, C-1) > right_max) return -1;
    int obs = query(lo, C-1);
    int cur = query(lo, B), res = 0;
    // cout << "cur: " << cur << " " << obs << " " << right_max << '\n';
    // int posi = pos[cur]; cout << las[posi] << " " << nex[posi] << '\n';
    for (int i = LG - 1; i >= 0; i--) {
        if (nxt[cur][i] < obs) {
            cur = nxt[cur][i];
            res += (1 << i);
        }
    }
    // cout << nxt[cur][0] << ' ' << nxt2[cur][0] << '\n';
    // cout << nxt2[14][0] << '\n';
    if (pos[nxt2[cur][0] >= C] && nxt2[cur][0] != n+1) return res+1;
    if (nxt[cur][0] != n+1 && h[nxt[cur][0]] < right_max) return res+2;
    for (int i = LG - 1; i >= 0; i--) {
        if (nxt2[cur][i] != n+1 && pos[nxt2[cur][i]] < C) {
            // cout << "cons: " << nxt2[cur][i] << " " << pos[nxt2[cur][i]] << '\n';
            cur = nxt2[cur][i];
            res += (1 << i);
        }
    }
    // cout << nxt2[cur][0] << " " << pos[nxt2[cur][0]] << ' ' << res << '\n';
    return res+1;
}

• Subtask 1: 4 / 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