Submission #595659

#	Time	Username	Problem	Language	Result	Execution time	Memory
595659		ocarima	Rainforest Jumps (APIO21_jumps)	C++14	100 / 100	1428 ms	45760 KiB

jumps

#include "jumps.h"
#include <vector>
#include<bits/stdc++.h>
 
using namespace std;
 
#define lli long long
#define rep(i, a, b) for(lli i = (a); i <= (b); ++i)
#define repa(i, a, b) for(lli i = (a); i >= (b); --i)
 
#define nl "\n"
#define debugsl(x) cout << #x << " = " << x << ", "
#define debug(x) debugsl(x) << nl
#define debugarr(x, a, b) cout << #x << " = ["; rep(ii, a, b){ cout << x[ii] << ", "; } cout << "]" << nl
 
#define MAX_N 200003
#define LOG_N 18
 
int izq[LOG_N][MAX_N], der[LOG_N][MAX_N], alto[LOG_N][MAX_N], pot[LOG_N];
int altura[MAX_N], n;
 
void init(int N, std::vector<int> H) {
    H.push_back(N + 1);
 
    pot[0] = 1;
    rep(i, 1, LOG_N - 1) pot[i] = pot[i - 1] * 2;
 
    n = N;
    rep(i, 0, N) altura[i + 1] = H[i];
    altura[0] = N + 1;
 
    stack<int> mq;
    rep(i, 0, N + 1){
        while (!mq.empty() && altura[mq.top()] < altura[i]) mq.pop();
        if (mq.empty()) izq[0][i] = i;
        else izq[0][i] = mq.top();
        mq.push(i);
    }
 
    while(!mq.empty()) mq.pop();
    repa(i, N + 1, 0){
        while (!mq.empty() && altura[mq.top()] < altura[i]) mq.pop();
        if (mq.empty()) der[0][i] = i;
        else der[0][i] = mq.top();
        mq.push(i);
    }
 
    der[0][0] = N + 1;
    izq[0][N + 1] = 0;
    rep(i, 1, N) alto[0][i] = (altura[izq[0][i]] > altura[der[0][i]]) ? izq[0][i] : der[0][i];
 
    rep(k, 1, LOG_N - 1){
        rep(i, 0, N + 1){
            izq[k][i] = izq[k - 1][izq[k - 1][i]];
            der[k][i] = der[k - 1][der[k - 1][i]];
            alto[k][i] = alto[k - 1][alto[k - 1][i]];
        }
    }
}
 
int alturamaxima(int l, int r){
    repa(k, LOG_N - 1, 0){
        if (der[k][l] <= r) l = der[k][l];
    }
    return l;
}
 
int minimum_jumps(int A, int B, int C, int D) {
 
    int medio, altmedio;
 
    A++; B++; C++; D++;
 
    if (B + 1 < C){
        medio = alturamaxima(B + 1, C - 1);
        altmedio = altura[medio];
    }
    else{
        medio = -1;
    }
 
    // NO HAY NADIE ENTRE A,B Y C,D
    if (medio == -1){
        if (der[0][B] <= D) return 1;
        else return -1;
    }
 
    // SI EL MAS ALTO EN MEDIO DE LOS RANGOS ES MAYOR QUE TODOS LOS DEL RANGO [C, D] ENTONCES ES IMPOSIBLE.
    if (der[0][medio] > D) return -1;
 
    // SI B > MAS ALTO DEL RANGO CENTRAL ENTONCES CUALQUIER ARBOL ORIGEN TENDRA QUE PASAR POR B O SER MAS ALTO QUE B
    // POR LO TANTO BASTA CON REVISAR SI B PUEDE LLEGAR DE UN SALTO, DE OTRA FORMA SERA IMPOSIBLE.
    if (altura[B] > altmedio){
        if (der[0][B] <= D) return 1;
        else return -1;
    }
 
    // BUSCA EL ARBOL MAS ALTO EN EL RANGO [A, B] QUE SEA MENOR QUE EL MAS ALTO DEL RANGO CENTRAL Y
    // QUE NO TENGA A LA DERECHA UNO MAS ALTO QUE EL DEL RANGO CENTRAL.
    int pos = B;
    repa(k, LOG_N - 1, 0){
        if (izq[k][pos] >= A && altura[izq[k][pos]] < altmedio) pos = izq[k][pos];
    }
 
    // VE SALTANDO SIEMPRE HACIA LA RAMA MAS ALTA SIEMPRE Y CUANDO ESTA SEA MENOR QUE LA MAS ALTA DEL RANGO CENTRAL.
    // ESTA RAMA POR FUERZA SIEMPRE TENDRA QUE ESTAR A LA IZQUIERDA DE LA MAS ALTA DE LA RAMA CENTRAL.
    int saltos = 0;
    int sig;
    repa(k, LOG_N - 1, 0){
        if (altura[alto[k][pos]] < altmedio){
            pos = alto[k][pos];
            saltos += pot[k];
         }
    }
 
    sig = izq[0][pos];
    if (sig >= A && sig <= B && der[0][sig] >= C && der[0][sig] <= D) return 1;
    if (sig < A && sig > 0 && der[0][sig] >= C && der[0][sig] <= D) return saltos + 2;
 
    repa(k, LOG_N - 1, 0){
        if (der[k][pos] < C){
            pos = der[k][pos];
            saltos += pot[k];
        }
    }
 
    if (der[0][pos] >= C && der[0][pos] <= D) return saltos + 1;
 
    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