oj.uz

Submission #438061

# Submission time Handle Problem Language Result Execution time Memory
438061 2021-06-27T13:32:30 Z cheeheng Rainforest Jumps (APIO21_jumps) C++14
0 / 100
 4000 ms 83448 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 best[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];
            }
        }
    }

    for(int i = 0; i < N; i ++){
        int X2 = i;
        int X3, X4;
        if(prevGreater[X2][0] == -1){
            X3 = prevGreater[X2][0];
            X4 = nextGreater[X2][0];
        }else if(nextGreater[X2][0] == M){
            X3 = nextGreater[X2][0];
            X4 = prevGreater[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];
        }
        best[i][0] = X3;
        if(best[i][0] == M){best[i][0] = -1;}
    }

    for(int k = 1; k < 20; k ++){
        for(int i = 0; i < N; i ++){
            if(best[i][k-1] == -1){
                best[i][k] = best[i][k-1];
            }else{
                best[i][k] = best[best[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 cutOffIndx = X;
    for(int k = 19; k >= 0; k --){
        if(nextGreater[cutOffIndx][k] != M && nextGreater[cutOffIndx][k] < C){
            cutOffIndx = nextGreater[cutOffIndx][k];
        }
    }
    cutOffIndx = nextGreater[cutOffIndx][0];
    assert(cutOffIndx >= C && cutOffIndx <= D);

    int ans = 0;

    int X5 = X;
    int totalDist = 0;
    for(int k = 19; k >= 0; k --){
        int temp = best[X5][k];
        if(temp != -1 && temp != M && val[temp] < val[cutOffIndx]){
            totalDist += (1<<k);
            X5 = temp;
        }
    }

    int X2 = X;
    totalDist = max(0, totalDist-5);
    ans += totalDist;
    for(int k = 19; k >= 0; k --){
        int temp = best[X2][k];
        if(temp != -1 && temp != M && totalDist >= (1<<k)){
            totalDist -= (1<<k);
            X2 = temp;
        }
    }

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

    return ans;
}

Compilation message

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:109:17: warning: variable 'X4' set but not used [-Wunused-but-set-variable]
  109 |         int X3, X4;
      |                 ^~

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 4011 ms 66352 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 1 ms 328 KB Output is correct
6 Correct 3 ms 328 KB Output is correct
7 Correct 3 ms 328 KB Output is correct
8 Correct 4 ms 328 KB Output is correct
9 Correct 2 ms 328 KB Output is correct
10 Correct 3 ms 328 KB Output is correct
11 Correct 4 ms 328 KB Output is correct
12 Correct 4 ms 328 KB Output is correct
13 Correct 3 ms 328 KB Output is correct
14 Correct 4 ms 328 KB Output is correct
15 Incorrect 4 ms 328 KB Output isn't correct
16 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 1 ms 328 KB Output is correct
6 Correct 3 ms 328 KB Output is correct
7 Correct 3 ms 328 KB Output is correct
8 Correct 4 ms 328 KB Output is correct
9 Correct 2 ms 328 KB Output is correct
10 Correct 3 ms 328 KB Output is correct
11 Correct 4 ms 328 KB Output is correct
12 Correct 4 ms 328 KB Output is correct
13 Correct 3 ms 328 KB Output is correct
14 Correct 4 ms 328 KB Output is correct
15 Incorrect 4 ms 328 KB Output isn't correct
16 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 168 ms 65812 KB Output is correct
6 Correct 205 ms 81856 KB Output is correct
7 Correct 110 ms 41920 KB Output is correct
8 Correct 207 ms 81680 KB Output is correct
9 Correct 17 ms 12488 KB Output is correct
10 Correct 204 ms 81700 KB Output is correct
11 Correct 206 ms 83376 KB Output is correct
12 Correct 202 ms 82964 KB Output is correct
13 Correct 197 ms 82912 KB Output is correct
14 Correct 214 ms 81824 KB Output is correct
15 Incorrect 219 ms 83448 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 0 ms 328 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 302 ms 37436 KB Output is correct
5 Incorrect 1176 ms 81828 KB Output isn't correct
6 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 328 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 302 ms 37436 KB Output is correct
5 Incorrect 1176 ms 81828 KB Output isn't correct
6 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 4011 ms 66352 KB Time limit exceeded
4 Halted 0 ms 0 KB -