Submission #416554

#	Time	Username	Problem	Language	Result	Execution time	Memory
416554		doowey	Rainforest Jumps (APIO21_jumps)	C++14	100 / 100	1364 ms	72444 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

const int N = (int)2e5 + 10;
const int LOG = 18;

int n;
vector<int> H;
pii tab[LOG][N];
int LG[N];

pii get(int lf, int rf){
    int ag = LG[rf - lf + 1];
    return max(tab[ag][lf], tab[ag][rf - (1 << ag) + 1]);
}

int lef[N];
int rig[N];
int any[LOG][N];
int big[LOG][N];
int tor[LOG][N];

void init(int _N, vector<int> _H) {
    n = _N;
    H = _H;
    for(int i = 0 ; i < n; i ++ ){
        tab[0][i] = mp(H[i], i);
    }
    vector<int> ids;
    for(int i = 0 ; i < n; i ++ ){
        while(!ids.empty() && H[i] > H[ids.back()]){
            ids.pop_back();
        }
        if(!ids.empty())
            lef[i] = ids.back();
        else
            lef[i] = -1;
        ids.push_back(i);
    }
    ids.clear();
    for(int i = n - 1; i >= 0 ; i -- ){
        while(!ids.empty() && H[i] > H[ids.back()]){
            ids.pop_back();
        }
        if(!ids.empty())
            rig[i] = ids.back();
        else
            rig[i] = -1;
        ids.push_back(i);
    }

    for(int i = 0 ; i < n; i ++ ){
        if(lef[i] == -1 || rig[i] == -1)
            any[0][i] = -1;
        else{
            big[0][i] = rig[i];
            if(H[lef[i]] > H[rig[i]]){
                any[0][i] = lef[i];
            }
            else{
                any[0][i] = rig[i];
            }
        }
        tor[0][i] = rig[i];
    }
    for(int i = 1; i < LOG; i ++ ){
        for(int j = 0 ; j < n; j ++ ){
            if(tor[i-1][j] == -1)
                tor[i][j] = -1;
            else
                tor[i][j] = tor[i-1][tor[i-1][j]];
        }
    }
    for(int i = 1 ; i < LOG; i ++ ){
        for(int j = 0 ; j < n ; j ++ ){
            if(any[i - 1][j] == -1){
                any[i][j] = -1;
            }
            else{
                big[i][j] = max(big[i-1][j], big[i-1][any[i-1][j]]);
                any[i][j] = any[i-1][any[i-1][j]];
            }
        }
    }

    int pak = 0;
    for(int i = 1; i <= n; i ++ ){
        while((1 << (pak + 1)) <= i){
            pak ++ ;
        }
        LG[i] = pak;
    }
    for(int lg = 1; lg < LOG; lg ++ ){
        for(int i = 0 ; i < n; i ++ ){
            if(i + (1 << lg) - 1 < n){
                tab[lg][i] = max(tab[lg-1][i], tab[lg-1][i + (1 << (lg - 1))]);
            }
        }
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    pii chk = get(C, D);
    pii bins = get(B, C - 1);
    if(bins.fi > chk.fi) return -1;
    int cur = B;
    int tr;
    for(int go = LOG - 1; go >= 0 ; go -- ){
        tr = cur - (1 << go);
        if(tr >= A){
            bins = get(tr, C - 1);
            if(bins.fi < chk.fi)
                cur = tr;
        }
    }


    pii ash = get(cur, B);
    B = ash.se;
    int moves = 0;
    for(int i = LOG - 1; i >= 0 ; i -- ){
        if(any[i][B] == -1) continue;
        if(big[i][B] >= C) continue;
        if(H[any[i][B]] > chk.fi) continue;
        B = any[i][B];
        moves += (1 << i);
    }
    for(int i = LOG - 1; i >= 0 ; i -- ){
        if(tor[i][B] == -1) continue;
        if(tor[i][B] < C){
            B = tor[i][B];
            moves += (1 << i);
        }
    }
    moves ++ ;
    return moves;
}

• 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