oj.uz

답안 #426186

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
426186 2021-06-13T15:03:36 Z ocarima 밀림 점프 (APIO21_jumps) C++14
0 / 100
 4000 ms 32176 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 maximo[LOG_N][MAX_N], minimo[LOG_N][MAX_N], n, pot[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];
    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
    maxorigen = 0;
    pmaxorigen = -1;
    rep(i, A, B){
        if (maximo[0][i] < maxdestino && maximo[0][i] > maxorigen){
            maxorigen = maximo[0][i];
            pmaxorigen = i;
        }
    }

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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1096 KB Output is correct
2 Correct 1 ms 1096 KB Output is correct
3 Execution timed out 4065 ms 26168 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1096 KB Output is correct
2 Correct 1 ms 1096 KB Output is correct
3 Correct 1 ms 1096 KB Output is correct
4 Correct 1 ms 1096 KB Output is correct
5 Incorrect 4 ms 1096 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1096 KB Output is correct
2 Correct 1 ms 1096 KB Output is correct
3 Correct 1 ms 1096 KB Output is correct
4 Correct 1 ms 1096 KB Output is correct
5 Incorrect 4 ms 1096 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1096 KB Output is correct
2 Correct 1 ms 1096 KB Output is correct
3 Correct 1 ms 1096 KB Output is correct
4 Correct 1 ms 1096 KB Output is correct
5 Correct 73 ms 25000 KB Output is correct
6 Correct 83 ms 31120 KB Output is correct
7 Correct 37 ms 15376 KB Output is correct
8 Correct 79 ms 31124 KB Output is correct
9 Correct 12 ms 5004 KB Output is correct
10 Correct 97 ms 31172 KB Output is correct
11 Correct 77 ms 32176 KB Output is correct
12 Correct 77 ms 31164 KB Output is correct
13 Correct 77 ms 31952 KB Output is correct
14 Correct 80 ms 31136 KB Output is correct
15 Correct 93 ms 31152 KB Output is correct
16 Correct 75 ms 31120 KB Output is correct
17 Correct 112 ms 31156 KB Output is correct
18 Correct 1 ms 1096 KB Output is correct
19 Correct 1 ms 1096 KB Output is correct
20 Correct 1 ms 1096 KB Output is correct
21 Correct 1 ms 1144 KB Output is correct
22 Incorrect 1 ms 1096 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1096 KB Output is correct
2 Correct 1 ms 1096 KB Output is correct
3 Correct 1 ms 1096 KB Output is correct
4 Correct 731 ms 14168 KB Output is correct
5 Execution timed out 4035 ms 31140 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1096 KB Output is correct
2 Correct 1 ms 1096 KB Output is correct
3 Correct 1 ms 1096 KB Output is correct
4 Correct 731 ms 14168 KB Output is correct
5 Execution timed out 4035 ms 31140 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1096 KB Output is correct
2 Correct 1 ms 1096 KB Output is correct
3 Execution timed out 4065 ms 26168 KB Time limit exceeded
4 Halted 0 ms 0 KB -