oj.uz

Submission #426983

# Submission time Handle Problem Language Result Execution time Memory
426983 2021-06-14T11:35:13 Z ocarima Rainforest Jumps (APIO21_jumps) C++14
0 / 100
 878 ms 45700 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);
    }

    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 minimum_jumps(int A, int B, int C, int D) {

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

    int medio = -1, altmedio = 0;
    rep(i, B + 1, C - 1){
        if (altura[i] > altmedio){
            altmedio = altura[i];
            medio = i;
        }
    }

    // NO HAY NADIE ENTRE A,B Y C,D
    if (medio == -1){
        if (der[0][B] <= D) return 1;
        else return -1;
    }

    if (der[0][medio] > D) return -1;

    // CALCULA SALTOS CON RAMA ALTA
    int saltos = 0;
    int pos = B, sig;
    repa(k, LOG_N - 1, 0){
        if (altura[alto[k][pos]] < altmedio){
            pos = alto[k][pos];
            saltos += pot[k];
            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 && der[0][sig] >= C && der[0][sig] <= D) return saltos + 2;

    repa(k, LOG_N - 1, 0){
        if (der[k][pos] <= D){
            pos = der[k][pos];
            saltos += pot[k];
            if (pos >= C && pos <= D) return saltos;
        }
    }

    return -1;
}

Subtask #1
0 / 4.0

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

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 584 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 52 ms 36516 KB Output is correct
6 Correct 67 ms 44832 KB Output is correct
7 Correct 38 ms 23292 KB Output is correct
8 Correct 62 ms 44804 KB Output is correct
9 Correct 10 ms 7368 KB Output is correct
10 Correct 61 ms 44848 KB Output is correct
11 Incorrect 57 ms 45700 KB Output isn't correct
12 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 878 ms 20824 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 878 ms 20824 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 632 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Incorrect 451 ms 36588 KB Output isn't correct
4 Halted 0 ms 0 KB -