oj.uz

Submission #427353

# Submission time Handle Problem Language Result Execution time Memory
427353 2021-06-14T14:30:19 Z ocarima Rainforest Jumps (APIO21_jumps) C++14
4 / 100
 1662 ms 45732 KB 
#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] = (H[izq[0][i]] > H[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];

            // SI EN EL CAMINO VOLVISTE
            if (pos >= A && pos <= B) saltos = 0;
        }
    }

    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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 584 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 219 ms 36656 KB Output is correct
4 Correct 1662 ms 45596 KB Output is correct
5 Correct 1523 ms 23340 KB Output is correct
6 Correct 1591 ms 45732 KB Output is correct
7 Correct 1174 ms 31496 KB Output is correct
8 Correct 1566 ms 45616 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 584 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 1 ms 548 KB Output is correct
4 Correct 1 ms 584 KB Output is correct
5 Incorrect 3 ms 584 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 584 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 1 ms 548 KB Output is correct
4 Correct 1 ms 584 KB Output is correct
5 Incorrect 3 ms 584 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 1 ms 584 KB Output is correct
4 Correct 1 ms 584 KB Output is correct
5 Correct 46 ms 36296 KB Output is correct
6 Correct 86 ms 44900 KB Output is correct
7 Correct 27 ms 23308 KB Output is correct
8 Correct 63 ms 44828 KB Output is correct
9 Correct 9 ms 7368 KB Output is correct
10 Correct 70 ms 44804 KB Output is correct
11 Correct 51 ms 45708 KB Output is correct
12 Correct 52 ms 45460 KB Output is correct
13 Incorrect 54 ms 45456 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 584 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 1 ms 584 KB Output is correct
4 Incorrect 319 ms 20904 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 584 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 1 ms 584 KB Output is correct
4 Incorrect 319 ms 20904 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 584 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 219 ms 36656 KB Output is correct
4 Correct 1662 ms 45596 KB Output is correct
5 Correct 1523 ms 23340 KB Output is correct
6 Correct 1591 ms 45732 KB Output is correct
7 Correct 1174 ms 31496 KB Output is correct
8 Correct 1566 ms 45616 KB Output is correct
9 Correct 1 ms 584 KB Output is correct
10 Correct 1 ms 584 KB Output is correct
11 Correct 1 ms 548 KB Output is correct
12 Correct 1 ms 584 KB Output is correct
13 Incorrect 3 ms 584 KB Output isn't correct
14 Halted 0 ms 0 KB -