oj.uz

Submission #437796

# Submission time Handle Problem Language Result Execution time Memory
437796 2021-06-27T06:14:11 Z cheeheng Rainforest Jumps (APIO21_jumps) C++14
0 / 100
 4000 ms 68156 KB 
#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> ii;

int nextGreater[200005][20];
int prevGreater[200005][20];
int indx[200005];
int log2_[200005];
ii val[200005][20];
int A1[200005];

int M;

void init2(){
    for(int i = 0; i < M; i ++){
        val[i][0] = ii(A1[i], i);
    }

    for(int k = 1; k < 20; k ++){
        for(int i = 0; i <= M-(1<<k); i ++){
            val[i][k] = max(val[i][k-1], val[i+(1<<(k-1))][k-1]);
        }
    }

    log2_[1] = 0;
    for(int i = 2; i <= M; i ++){
        log2_[i] = log2_[i>>1] + 1;
    }
}

ii findMax(int l, int r){
    int k = log2_[r-l+1];
    return max(val[l][k], val[r-(1<<k)+1][k]);
}

void init(int N, std::vector<int> H){
    M = N;

    for(int i = 0; i < N; i ++){
        A1[i] = H[i];
    }

    init2();

    for(int i = 0; i < N; i ++){
        nextGreater[i][0] = N;
        prevGreater[i][0] = -1;
    }

    vector<ii> stack1 = vector<ii>();
    for(int i = 0; i < N; i ++){
        while(!stack1.empty()){
            ii temp = stack1.back();

            if(temp.first < H[i]){
                nextGreater[temp.second][0] = i;
                stack1.pop_back();
            }else{
                break;
            }
        }
        stack1.emplace_back(H[i], i);
    }

    stack1 = vector<ii>();
    for(int i = N-1; i >= 0; i --){
        while(!stack1.empty()){
            ii temp = stack1.back();

            if(temp.first < H[i]){
                prevGreater[temp.second][0] = i;
                stack1.pop_back();
            }else{
                break;
            }
        }
        stack1.emplace_back(H[i], i);
    }

    /*for(int i = 0; i < N; i ++){
        printf("nextGreater[%d]=%d\n", i, nextGreater[i][0]);
    }

    for(int i = 0; i < N; i ++){
        printf("prevGreater[%d]=%d\n", i, prevGreater[i][0]);
    }*/

    for(int k = 1; k < 20; k ++){
        for(int i = 0; i < N; i ++){
            if(nextGreater[i][k-1] == N){
                nextGreater[i][k] = N;
            }else{
                nextGreater[i][k] = nextGreater[nextGreater[i][k-1]][k-1];
            }

            if(prevGreater[i][k-1] == -1){
                prevGreater[i][k] = -1;
            }else{
                prevGreater[i][k] = prevGreater[prevGreater[i][k-1]][k-1];
            }
        }
    }
}

int minimum_jumps(int A, int B, int C, int D){
    assert(0 <= A && A <= B && B < C && C <= D && D <= M-1);

    ii maxValCD = findMax(C, D);
    int maxIndxCD = prevGreater[maxValCD.second][0];
    //printf("maxValCD=%d\n", maxValCD);
    A = max(maxIndxCD+1, A);

    if(A > B){return -1;}

    ii maxValAB = findMax(A, B);
    int X = maxValAB.second;

    int ans = 0;
    int X2 = X;

    while(X2 < C){
        int X3, X4;
        if(prevGreater[X2][0] == -1){
            X3 = nextGreater[X2][0];
            X4 = prevGreater[X2][0];
        }else if(nextGreater[X2][0] == M){
            X3 = prevGreater[X2][0];
            X4 = nextGreater[X2][0];
        }else if(A1[prevGreater[X2][0]] > A1[nextGreater[X2][0]]){
            X3 = prevGreater[X2][0];
            X4 = nextGreater[X2][0];
        }else{
            X3 = nextGreater[X2][0];
            X4 = prevGreater[X2][0];
        }

        //printf("X2=%d; X3=%d; X4=%d\n", X2, X3, X4);
        if(A1[X3] > maxValCD.first){
            X2 = X4;
        }else{
            X2 = X3;
        }
        //printf("X2=%d\n", X2);
        ans ++;
        assert(X2 >= 0 && X2 < M);
    }

    return ans;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Execution timed out 4027 ms 54712 KB Time limit exceeded
4 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 1 ms 328 KB Output is correct
3 Correct 1 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 4 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 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 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 4 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 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 142 ms 53208 KB Output is correct
6 Correct 203 ms 66040 KB Output is correct
7 Correct 97 ms 33956 KB Output is correct
8 Correct 189 ms 66040 KB Output is correct
9 Correct 15 ms 10184 KB Output is correct
10 Correct 191 ms 65984 KB Output is correct
11 Correct 195 ms 68120 KB Output is correct
12 Correct 170 ms 68156 KB Output is correct
13 Correct 164 ms 68120 KB Output is correct
14 Correct 174 ms 66076 KB Output is correct
15 Incorrect 214 ms 67728 KB Output isn't correct
16 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 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 313 ms 30272 KB Output is correct
5 Correct 1273 ms 65988 KB Output is correct
6 Correct 624 ms 11044 KB Output is correct
7 Correct 1316 ms 65956 KB Output is correct
8 Correct 823 ms 22848 KB Output is correct
9 Correct 1262 ms 65968 KB Output is correct
10 Execution timed out 4067 ms 68148 KB Time limit exceeded
11 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 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 313 ms 30272 KB Output is correct
5 Correct 1273 ms 65988 KB Output is correct
6 Correct 624 ms 11044 KB Output is correct
7 Correct 1316 ms 65956 KB Output is correct
8 Correct 823 ms 22848 KB Output is correct
9 Correct 1262 ms 65968 KB Output is correct
10 Execution timed out 4067 ms 68148 KB Time limit exceeded
11 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 1 ms 328 KB Output is correct
3 Execution timed out 4027 ms 54712 KB Time limit exceeded
4 Halted 0 ms 0 KB -