oj.uz

Submission #416543

# Submission time Handle Problem Language Result Execution time Memory
416543 2021-06-02T15:10:46 Z doowey Rainforest Jumps (APIO21_jumps) C++14
0 / 100
 4000 ms 32000 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

const int N = (int)2e5 + 10;
const int LOG = 18;

int n;
vector<int> H;
pii tab[LOG][N];
int LG[N];

pii get(int lf, int rf){
    int ag = LG[rf - lf + 1];
    return max(tab[ag][lf], tab[ag][rf - (1 << ag) + 1]);
}

int lef[N];
int rig[N];

void init(int _N, vector<int> _H) {
    n = _N;
    H = _H;
    for(int i = 0 ; i < n; i ++ ){
        tab[0][i] = mp(H[i], i);
    }
    vector<int> ids;
    for(int i = 0 ; i < n; i ++ ){
        while(!ids.empty() && H[i] > H[ids.back()]){
            ids.pop_back();
        }
        if(!ids.empty())
            lef[i] = ids.back();
        else
            lef[i] = -1;
        ids.push_back(i);
    }
    ids.clear();
    for(int i = n - 1; i >= 0 ; i -- ){
        while(!ids.empty() && H[i] > H[ids.back()]){
            ids.pop_back();
        }
        if(!ids.empty())
            rig[i] = ids.back();
        else
            rig[i] = -1;
        ids.push_back(i);
    }
    int pak = 0;
    for(int i = 1; i <= n; i ++ ){
        while((1 << (pak + 1)) <= i){
            pak ++ ;
        }
        LG[i] = pak;
    }
    for(int lg = 1; lg < LOG; lg ++ ){
        for(int i = 0 ; i < n; i ++ ){
            if(i + (1 << lg) - 1 < n){
                tab[lg][i] = max(tab[lg-1][i], tab[lg-1][i + (1 << (lg - 1))]);
            }
        }
    }
}

int dep[N];

int minimum_jumps(int A, int B, int C, int D) {
    pii chk = get(C, D);
    pii bins = get(B, C - 1);
    if(bins.fi > chk.fi) return -1;
    int cur = B;
    int tr;
    for(int go = LOG - 1; go >= 0 ; go -- ){
        tr = cur - (1 << go);
        if(tr >= A){
            bins = get(tr, C - 1);
            if(bins.fi < chk.fi)
                cur = tr;
        }
    }
    pii ash = get(cur, B);
    B = ash.se;
    for(int i = 0 ; i < n; i ++ ){
        dep[i] = (int)1e9;
    }
    dep[B] = 0;
    queue<int> opt;
    opt.push(B);
    while(!opt.empty()){
        B = opt.front();
        if(B >= C){
            return dep[B];
        }
        opt.pop();

        if(lef[B] >= 0 && dep[B] + 1 < dep[lef[B]]){
            dep[lef[B]] = dep[B] + 1;
            opt.push(lef[B]);
        }
        if(rig[B] >= 0 && dep[B] + 1 < dep[rig[B]]){
            dep[rig[B]] = dep[B] + 1;
            opt.push(rig[B]);
        }
    }

    return -1111;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Execution timed out 4018 ms 25232 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Correct 44 ms 24700 KB Output is correct
6 Correct 55 ms 31120 KB Output is correct
7 Correct 33 ms 15384 KB Output is correct
8 Correct 53 ms 31152 KB Output is correct
9 Correct 8 ms 4424 KB Output is correct
10 Correct 56 ms 31152 KB Output is correct
11 Correct 48 ms 32000 KB Output is correct
12 Incorrect 47 ms 31748 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Incorrect 242 ms 13656 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 328 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Incorrect 242 ms 13656 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 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Execution timed out 4018 ms 25232 KB Time limit exceeded
4 Halted 0 ms 0 KB -