oj.uz

Submission #438067

# Submission time Handle Problem Language Result Execution time Memory
438067 2021-06-27T13:38:10 Z cheeheng Rainforest Jumps (APIO21_jumps) C++14
0 / 100
 4000 ms 164140 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 = 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];
        }
        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 && val[temp] < val[cutOffIndx]){
            totalDist += (1<<k);
            X5 = temp;
        }
    }

    int X2 = X;
    totalDist = max(0, totalDist-(D-A+1));
    ans += totalDist;
    for(int k = 19; k >= 0; k --){
        int temp = best[X2][k];
        if(temp != -1 && 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 4074 ms 66444 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 3 ms 328 KB Output is correct
6 Correct 3 ms 436 KB Output is correct
7 Correct 4 ms 328 KB Output is correct
8 Correct 3 ms 328 KB Output is correct
9 Correct 2 ms 328 KB Output is correct
10 Correct 4 ms 328 KB Output is correct
11 Correct 2 ms 328 KB Output is correct
12 Correct 4 ms 328 KB Output is correct
13 Correct 4 ms 328 KB Output is correct
14 Correct 4 ms 328 KB Output is correct
15 Incorrect 3 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 3 ms 328 KB Output is correct
6 Correct 3 ms 436 KB Output is correct
7 Correct 4 ms 328 KB Output is correct
8 Correct 3 ms 328 KB Output is correct
9 Correct 2 ms 328 KB Output is correct
10 Correct 4 ms 328 KB Output is correct
11 Correct 2 ms 328 KB Output is correct
12 Correct 4 ms 328 KB Output is correct
13 Correct 4 ms 328 KB Output is correct
14 Correct 4 ms 328 KB Output is correct
15 Incorrect 3 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 158 ms 65688 KB Output is correct
6 Correct 206 ms 81672 KB Output is correct
7 Correct 98 ms 41872 KB Output is correct
8 Correct 202 ms 81584 KB Output is correct
9 Correct 17 ms 12536 KB Output is correct
10 Correct 200 ms 81676 KB Output is correct
11 Correct 197 ms 83372 KB Output is correct
12 Correct 208 ms 82864 KB Output is correct
13 Correct 200 ms 82908 KB Output is correct
14 Correct 215 ms 81580 KB Output is correct
15 Correct 220 ms 83460 KB Output is correct
16 Correct 196 ms 81892 KB Output is correct
17 Correct 222 ms 82056 KB Output is correct
18 Correct 1 ms 328 KB Output is correct
19 Correct 1 ms 328 KB Output is correct
20 Correct 1 ms 328 KB Output is correct
21 Correct 1 ms 328 KB Output is correct
22 Correct 1 ms 328 KB Output is correct
23 Correct 1 ms 328 KB Output is correct
24 Correct 1 ms 328 KB Output is correct
25 Correct 1 ms 328 KB Output is correct
26 Correct 1 ms 584 KB Output is correct
27 Correct 2 ms 1096 KB Output is correct
28 Correct 2 ms 1096 KB Output is correct
29 Correct 2 ms 1096 KB Output is correct
30 Correct 2 ms 1096 KB Output is correct
31 Correct 1 ms 1096 KB Output is correct
32 Correct 1 ms 328 KB Output is correct
33 Correct 208 ms 81512 KB Output is correct
34 Correct 210 ms 81672 KB Output is correct
35 Correct 210 ms 83080 KB Output is correct
36 Correct 216 ms 81672 KB Output is correct
37 Correct 222 ms 83448 KB Output is correct
38 Runtime error 291 ms 164140 KB Execution killed with signal 6
39 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 Runtime error 218 ms 75204 KB Execution killed with signal 6
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 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Runtime error 218 ms 75204 KB Execution killed with signal 6
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 1 ms 328 KB Output is correct
3 Execution timed out 4074 ms 66444 KB Time limit exceeded
4 Halted 0 ms 0 KB -