oj.uz

Submission #1035826

# Submission time Handle Problem Language Result Execution time Memory
1035826 2024-07-26T16:28:17 Z _8_8_ Rainforest Jumps (APIO21_jumps) C++17
0 / 100
 150 ms 31356 KB 
#include "jumps.h"
 
#include <vector>
#include <bits/stdc++.h>
using namespace std;
 
const int B = 20;
int n;
vector<vector<int>> build(vector<vector<int>> g,vector<int>rt){
    vector<vector<int>> up(n+1);
    function<void(int,int )> dfs = [&](int v,int pr) {
        up[v].resize(B);
        up[v][0] = pr;
        for(int i = 1;i < B;i++){
            up[v][i] = up[up[v][i - 1]][i - 1];
        }
        for(int to:g[v]) {  
            dfs(to,v);
        }
    };
    for(int i:rt) {
        dfs(i,i);
    }
    return up;
}
vector<vector<int>> up,up1;
const int maxn = (int)1e5 + 12;
int l[maxn],r[maxn];
vector<int> h;
void init(int N, vector<int> H) {
    h = H;
    n = N;
    vector<int> st,rt;
    vector<vector<int>> G(n);
    for(int i = 0;i < N;i++) {
        while(!(int)st.empty() && H[st.back()] < H[i]) {
            st.pop_back();
        }
        if(st.empty()){
            rt.push_back(i);
            l[i] = -1;
        }else {
            G[st.back()].push_back(i);            
            l[i] = st.back();
        }
        st.push_back(i);
    }
    up = build(G,rt);
    for(int i = 0;i < n;i++){
        G[i].clear();
    }
    rt.clear();
    st.clear();
    for(int i = N - 1;i >= 0;i--){
        while(!st.empty() && H[st.back()] < H[i]){
            st.pop_back();
        }
        if(st.empty()){
            rt.push_back(i);
            r[i] = -1;
        }else {
            G[st.back()].push_back(i);
            r[i] = st.back();
        }
        st.push_back(i);
    }
    up1 = build(G,rt);
}
bool check(int ver,int C,int D){
    while(true)
    {
        if(ver >= C && ver <= D) return 1;
        if(r[ver] == -1) return 0;
        ver = r[ver];
    }
    // for(int i = B - 1;i >= 0;i--){
    //     if(up1[ver][i] < C){
    //         ver = up1[ver][i];
    //     }
    // }
    // ver = up1[ver][0];
    // return (ver >= C && ver <= D);
}
int go(int ver,int C,int D) {
    if(ver >= C && ver <= D) return 0;
    // assert(r[ver] != -1 && check(r[ver],C,D));
    if(1 || l[ver] == -1 || h[r[ver]] > h[l[ver]] || !check(l[ver],C,D)){
        return go(r[ver],C,D) + 1;
    }
    return go(l[ver],C,D) + 1;
}
int minimum_jumps(int A, int B, int C, int D) {
    int res = 1e9;
    for(int i = B;i <= B;i++) {
        if(check(i,C,D)){
            res = min(res,go(i,C,D));
        }
    }
    // int ver = B;
    // for(int i = 19;i >= 0;i--){
    //     if(up[ver][i] >= A && check(ver,C,D) != -1){
    //         ver = up[ver][i];
    //     }
    // }
    if(res == 1e9) res = -1;
    return res;
    // if(!check(ver,C,D)){
    //     return -1;
    // }
    // return go(ver,C,D);
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Runtime error 17 ms 13612 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Incorrect 1 ms 344 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Incorrect 1 ms 344 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Runtime error 22 ms 16184 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 150 ms 31356 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 150 ms 31356 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Runtime error 17 ms 13612 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -