oj.uz

답안 #427032

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
427032 2021-06-14T11:55:32 Z ocarima 밀림 점프 (APIO21_jumps) C++14
4 / 100
 1813 ms 45716 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;
    }

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

    if (altura[B] > altmedio){
        if (der[0][B] <= D) return 1;
        else 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 && 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 584 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 239 ms 36620 KB Output is correct
4 Correct 1675 ms 45668 KB Output is correct
5 Correct 1422 ms 23348 KB Output is correct
6 Correct 1466 ms 45716 KB Output is correct
7 Correct 1337 ms 31524 KB Output is correct
8 Correct 1813 ms 45616 KB Output is correct

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 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 Incorrect 2 ms 584 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 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 Incorrect 2 ms 584 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 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 61 ms 36380 KB Output is correct
6 Correct 79 ms 44832 KB Output is correct
7 Correct 36 ms 23300 KB Output is correct
8 Correct 68 ms 44832 KB Output is correct
9 Correct 12 ms 7348 KB Output is correct
10 Correct 60 ms 44848 KB Output is correct
11 Correct 64 ms 45652 KB Output is correct
12 Correct 52 ms 45460 KB Output is correct
13 Incorrect 68 ms 45440 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 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 277 ms 20904 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# 결과 실행 시간 메모리 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 277 ms 20904 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 584 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 239 ms 36620 KB Output is correct
4 Correct 1675 ms 45668 KB Output is correct
5 Correct 1422 ms 23348 KB Output is correct
6 Correct 1466 ms 45716 KB Output is correct
7 Correct 1337 ms 31524 KB Output is correct
8 Correct 1813 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 584 KB Output is correct
12 Correct 1 ms 584 KB Output is correct
13 Incorrect 2 ms 584 KB Output isn't correct
14 Halted 0 ms 0 KB -