Submission #426210

#	Time	Username	Problem	Language	Result	Execution time	Memory
426210		ocarima	Rainforest Jumps (APIO21_jumps)	C++14	33 / 100	4062 ms	32976 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 maximo[LOG_N][MAX_N], minimo[LOG_N][MAX_N], n, pot[MAX_N], posicion[MAX_N];
int izq[MAX_N], der[MAX_N];
int k, res;

int maxrango(int l, int r){
    k = pot[r - l + 1];
    return max(maximo[k][l], maximo[k][r - (1 << k) + 1]);
}

int minrango(int l, int r){
    k = pot[r - l + 1];
    return min(minimo[k][l], minimo[k][r - (1 << k) + 1]);
}

void init(int N, std::vector<int> H) {
    int p = 1, k = 0;
    n = N;
    rep(i, 0, n - 1) { maximo[0][i + 1] = minimo[0][i + 1] = H[i], posicion[H[i]] = i + 1; }
    maximo[0][0] = maximo[0][n + 1] = minimo[0][0] = minimo[0][n + 1] = n + 1;

    rep(k, 1, LOG_N - 1){
        rep(i, 0, (n + 1) - p - p + 1){
            maximo[k][i] = max(maximo[k - 1][i], maximo[k - 1][i + p]);
            minimo[k][i] = min(minimo[k - 1][i], minimo[k - 1][i + p]);
        }
        p <<= 1;
    }

    p = 1;
    rep(i, 1, MAX_N - 1){
        pot[i] = k;
        if (p + p <= i){ p <<= 1; ++k; }
    }

    // OBTEN EL SIGUIENTE SALTO A LA DERECHA Y A LA IZQUIERDA DE CADA NUMERO
    int l, r, mitad, cur;
    rep(i, 1, n){
        // OBTEN SU SALTO A LA IZQUIERDA;
        l = 0;
        r = i - 1;
        cur = l;
        while (l <= r){
            mitad = (l + r) / 2;
            if (maxrango(mitad, i - 1) > H[i - 1]){
                l = mitad + 1;
                cur = mitad;
            }
            else r = mitad - 1;
        }
        izq[i] = cur;

        // OBTEN SU SALTO A LA DERECHA;
        l = i + 1;
        r = n + 1;
        cur = n + 1;
        while (l <= r){
            mitad = (l + r) / 2;
            if (maxrango(i + 1, mitad) > H[i - 1]){
                r = mitad - 1;
                cur = mitad;
            }
            else l = mitad + 1;
        }
        der[i] = cur;
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    res = n + 1;

    ++A; ++B; ++C; ++D;

    int maxdestino, maxorigen, pmaxorigen, cntsalto;
    int cnt, pos, hi, hd;
    vector<int> mindist(n + 2, 0);

    maxdestino = (maxrango(C, D));

    // OBTEN EL MAS A LA IZQUIERDA MENOR QUE EL MAYOR
    int l, r, mitad, cur;
    l = A;
    r = B;
    cur = B;
    while (l <= r){
        mitad = (l + r) / 2;
        if (maxrango(mitad, B) < maxdestino){
            cur = mitad;
            r = mitad - 1;
        }
        else l = mitad + 1;
    }
    maxorigen = maxrango(cur, B);

    pmaxorigen = posicion[maxorigen];

    rep(i, pmaxorigen, pmaxorigen){
        pos = i;
        cnt = 0;
        vector<int> saltos;
        saltos.push_back(pos);
        while (pos != 0 && pos != n + 1){

            hi = maximo[0][izq[pos]];
            hd = maximo[0][der[pos]];

            if (der[pos] >= C && der[pos] <= D) pos = der[pos];
            else if (hi > hd && hi < maxdestino) pos = izq[pos];
            else if (hd > hi && hd < maxdestino) pos = der[pos];
            else if (hi > hd && hd < maxdestino) pos = der[pos];
            else if (hd > hi && hi < maxdestino) pos = izq[pos];
            else{
                cnt = n + 1;
                break;
            }

            ++cnt;
            saltos.push_back(pos);

            if (mindist[pos] > 0){
                cnt += mindist[pos];
                res = min(res, cnt);
                cntsalto = mindist[pos];
                saltos.pop_back();
                while(saltos.size()){
                    cntsalto++;
                    mindist[saltos.back()] = cntsalto;
                    saltos.pop_back();
                }
                break;
            }

            if (pos >= C && pos <= D){
                res = min(res, cnt);
                cntsalto = 0;
                while (saltos.size()){
                    mindist[saltos.back()] = cntsalto++;
                    saltos.pop_back();
                }
                break;
            }
        }
    }

    return (res == n + 1) ? -1 : res;
}

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