oj.uz

Submission #430521

# Submission time Handle Problem Language Result Execution time Memory
430521 2021-06-16T15:17:28 Z Sorting Rainforest Jumps (APIO21_jumps) C++17
0 / 100
 4000 ms 36276 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];
        }
    }
    if(valid(big_nxt[0][idx]) && right_nxt[0][idx] < c){
        ++ans;
        idx = big_nxt[0][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 1323 ms 29084 KB Output is correct
4 Execution timed out 4016 ms 36276 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 2 ms 456 KB Output is correct
6 Incorrect 2 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 2 ms 456 KB Output is correct
6 Incorrect 2 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 47 ms 28704 KB Output is correct
6 Correct 65 ms 35500 KB Output is correct
7 Correct 38 ms 18492 KB Output is correct
8 Correct 61 ms 35480 KB Output is correct
9 Correct 11 ms 5704 KB Output is correct
10 Correct 62 ms 35500 KB Output is correct
11 Correct 65 ms 36264 KB Output is correct
12 Incorrect 61 ms 35832 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 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 959 ms 16516 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 959 ms 16516 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 1323 ms 29084 KB Output is correct
4 Execution timed out 4016 ms 36276 KB Time limit exceeded
5 Halted 0 ms 0 KB -