oj.uz

Submission #416537

# Submission time Handle Problem Language Result Execution time Memory
416537 2021-06-02T15:03:38 Z doowey Rainforest Jumps (APIO21_jumps) C++14
0 / 100
 4000 ms 32052 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 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;
    int moves = 0;
    while(1){
        if(rig[B] >= C){
            B = rig[B];
            moves ++ ;
            break;
        }
        if(lef[B] == -1) {
            B = rig[B];
            moves ++ ;
            continue;
        }
        if(rig[B] == -1){
            B = lef[B];
            moves ++ ;
            continue;
        }
        if(H[lef[B]] > H[rig[B]]){
            B = lef[B];
            moves ++ ;
        }
        else{
            B = rig[B];
            moves ++ ;
        }
    }
    return moves;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 1303 ms 25140 KB Output is correct
4 Execution timed out 4025 ms 32044 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.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 Correct 0 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Execution timed out 4072 ms 328 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.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 Correct 0 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Execution timed out 4072 ms 328 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Correct 44 ms 24780 KB Output is correct
6 Correct 57 ms 31128 KB Output is correct
7 Correct 28 ms 15296 KB Output is correct
8 Correct 58 ms 31064 KB Output is correct
9 Correct 8 ms 4296 KB Output is correct
10 Correct 57 ms 31140 KB Output is correct
11 Correct 48 ms 32052 KB Output is correct
12 Incorrect 46 ms 31752 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 232 ms 13600 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 232 ms 13600 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 200 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 1303 ms 25140 KB Output is correct
4 Execution timed out 4025 ms 32044 KB Time limit exceeded
5 Halted 0 ms 0 KB -