oj.uz

Submission #429232

# Submission time Handle Problem Language Result Execution time Memory
429232 2021-06-15T19:14:39 Z Sorting Rainforest Jumps (APIO21_jumps) C++17
0 / 100
 4000 ms 36272 KB 
#include "jumps.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 3;
const int LOGN = 20;

int n, h[N];
int right_nxt[LOGN][N], big_nxt[LOGN][N];
int r[N], l[N];

void build_l_r(){
    stack<int> st;

    for(int i = 0; i < n; ++i){
        while(!st.empty() && h[i] > h[st.top()]){
            r[st.top()] = i;
            st.pop();
        }
        st.push(i);
    }
    while(!st.empty()){
        r[st.top()] = n;
        st.pop();
    }

    for(int i = n - 1; i >= 0; --i){
        while(!st.empty() && h[i] > h[st.top()]){
            l[st.top()] = i;
            st.pop();
        }
        st.push(i);
    }
    while(!st.empty()){
        l[st.top()] = -1;
        st.pop();
    }
}

bool valid(int pos){
    return pos >= 0 && pos < n;
}

void init(int _n, vector<int> _h){
    n = _n;
    for(int i = 0; i < n; ++i)
        h[i] = _h[i];

    build_l_r();
    for(int i = 0; i < n; ++i)
        right_nxt[0][i] = r[i];
    for(int i = 0; i < n; ++i){
        if(l[i] == -1 || r[i] == n){
            big_nxt[0][i] = (l[i] == -1) ? l[i] : r[i];
        }
        else{
            big_nxt[0][i] = (h[l[i]] > h[r[i]]) ? l[i] : r[i];
        }
    }

    for(int j = 1; j < LOGN; ++j){
        for(int i = 0; i < n; ++i){
            if(!valid(big_nxt[j - 1][i])) big_nxt[j][i] = big_nxt[j - 1][i];
            else big_nxt[j][i] = big_nxt[j - 1][big_nxt[j - 1][i]];
            
            if(!valid(right_nxt[j - 1][i])) right_nxt[j][i] = right_nxt[j - 1][i];
            else right_nxt[j][i] = right_nxt[j - 1][right_nxt[j - 1][i]];
        }
    }
}

int minimum_jumps(int a, int b, int c, int d){
    int mx2 = 0;
    for(int i = c; i <= d; ++i)
        mx2 = max(mx2, h[i]);

    int mx_mid = 0;
    for(int i = b + 1; i <= c - 1; ++i)
        if(h[i] > mx_mid)
            mx_mid = h[i];
    if(mx_mid > mx2) return -1; 

    int mx1 = 0, idx = -1;
    for(int i = b; i >= a; --i){
        if(h[i] > mx2) break;
        if(h[i] > mx1){
            mx1 = h[i];
            idx = i;
        }
    }

    if(!mx1) return -1;

    int ans = 0;
    for(int i = LOGN - 1; i >= 0; --i){
        if(valid(big_nxt[i][idx]) && h[big_nxt[i][idx]] <= mx_mid){
            ans += 1 << i;
            idx = big_nxt[i][idx];
        }
    }
    for(int i = LOGN - 1; i >= 0; --i){
        if(valid(right_nxt[i][idx]) && right_nxt[i][idx] < c){
            ans += 1 << i;
            idx = right_nxt[i][idx];
        }
    }
    return ans + 1;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 1318 ms 29068 KB Output is correct
4 Execution timed out 4083 ms 36272 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 456 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Correct 3 ms 456 KB Output is correct
6 Incorrect 3 ms 456 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 456 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Correct 3 ms 456 KB Output is correct
6 Incorrect 3 ms 456 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 456 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Correct 48 ms 28792 KB Output is correct
6 Correct 58 ms 35424 KB Output is correct
7 Correct 28 ms 18464 KB Output is correct
8 Correct 70 ms 35472 KB Output is correct
9 Correct 9 ms 5716 KB Output is correct
10 Correct 61 ms 35392 KB Output is correct
11 Correct 55 ms 36244 KB Output is correct
12 Correct 54 ms 35836 KB Output is correct
13 Incorrect 49 ms 36080 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Incorrect 901 ms 16536 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 456 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Incorrect 901 ms 16536 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 456 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 1318 ms 29068 KB Output is correct
4 Execution timed out 4083 ms 36272 KB Time limit exceeded
5 Halted 0 ms 0 KB -