Submission #501324

#	Time	Username	Problem	Language	Result	Execution time	Memory
501324		Victor	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	1440 ms	59792 KiB

jumps

// #pragma GCC optimize ("Ofast,inline") // O1 
// #pragma GCC target ("avx,avx2,fma")- O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")

#include <bits/stdc++.h>

#include "jumps.h"

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout<<#x<<" = "<<x<<endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;

int jmp[18][200001], jmpL[18][200001], jmpR[18][200001], sparse[18][200001];
int arr[200001], h[200001], n;

int rmq(int lo, int hi) {
    int twopow = log2(hi - lo + 1);
    return max(sparse[twopow][lo], sparse[twopow][hi - (1 << twopow) + 1]);
}

void init(int N, std::vector<int> H) {
    n = N;
    rep(i, 0, n) h[i] = H[i];

    int pos = -1;
    rep(i, 0, n) {
        while (pos != -1 && H[i] > H[arr[pos]]) --pos;
        ++pos;
        arr[pos] = i;
        jmpL[0][i] = arr[max(0, pos - 1)];
    }

    pos = -1;
    per(i, 0, n) {
        while (pos != -1 && H[i] > H[arr[pos]]) --pos;
        ++pos;
        arr[pos] = i;
        jmpR[0][i] = arr[max(0, pos - 1)];
    }

    rep(i, 0, n) {
        jmp[0][i] = H[jmpL[0][i]] > H[jmpR[0][i]] ? jmpL[0][i] : jmpR[0][i];
        sparse[0][i] = h[i];
    }

    rep(j, 1, 18) rep(i, 0, n) {
        jmpL[j][i] = jmpL[j - 1][jmpL[j - 1][i]];
        jmpR[j][i] = jmpR[j - 1][jmpR[j - 1][i]];
        jmp[j][i] = jmp[j - 1][jmp[j - 1][i]];
        sparse[j][i] = max(sparse[j - 1][i], sparse[j - 1][min(n - 1, i + (1 << j - 1))]);
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    if ((A <= C && C <= B) || (A <= D && D <= B) || (C <= A && B <= D)) return 0;
    int maxCD = rmq(C, D);
    int max_between = B < C ? rmq(B, C - 1) : rmq(D + 1, A);
    //cout<<maxCD<<' '<<max_between<<endl;
    assert(maxCD != max_between);
    if (max_between > maxCD) return -1;

    int cur_pos;
    if (B < C) {
        cur_pos = B;
        per(j, 0, 18) if (jmpL[j][cur_pos] >= A && h[jmpL[j][cur_pos]] < maxCD) cur_pos = jmpL[j][cur_pos];

    } else {
        cur_pos = A;
        per(j, 0, 18) if ( jmpL[j][cur_pos] <= B && h[jmpR[j][cur_pos]] < maxCD) cur_pos = jmpR[j][cur_pos];
    }

    //debug(cur_pos);

    int ans = 0;
    per(j, 0, 18) if (h[jmp[j][cur_pos]] < max_between) {
        ans += 1 << j;
        cur_pos = jmp[j][cur_pos];
    }

    int p1 = cur_pos, p2 = cur_pos;
    int cnt1 = 0, cnt2 = 1;
    if (B < C) {
        //debug(cur_pos);
        p2 = jmpL[0][cur_pos];
        if (h[p2] > maxCD) cnt2 = INF;
        per(j, 0, 18) {
            if (jmpR[j][p1] < C) {
                cnt1 += 1 << j;
                p1 = jmpR[j][p1];
            }

            if (jmpR[j][p2] < C) {
                cnt2 += 1 << j;
                p2 = jmpR[j][p2];
            }
        }
    }

    else {
        p2 = jmpR[0][cur_pos];
        if (h[p2] > maxCD) cnt2 = INF;
        per(j, 0, 18) {
            if (jmpL[j][p1] < C) {
                cnt1 += 1 << j;
                p1 = jmpL[j][p1];
            }

            if (jmpL[j][p2] < C) {
                cnt2 += 1 << j;
                p2 = jmpL[j][p2];
            }
        }
    }

    ans += min(cnt1, cnt2) + 1;
    return ans;
}

Compilation message (stderr)

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:73:83: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   73 |         sparse[j][i] = max(sparse[j - 1][i], sparse[j - 1][min(n - 1, i + (1 << j - 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