oj.uz

Submission #737288

# Submission time Handle Problem Language Result Execution time Memory
737288 2023-05-07T04:03:46 Z phoebe Rainforest Jumps (APIO21_jumps) C++17
0 / 100
 4000 ms 17432 KB 
#include <bits/stdc++.h>
#include "jumps.h"
using namespace std;

#define ll long long
#define pii pair<int, int>
#define F first
#define S second
#define FOR(i, n) for (int i = 0; i < n; i++)
#define PB push_back

const int maxn = 2e5 + 10, INF = 1e9 + 7;
int n, h[maxn], tree[maxn * 4], jump[maxn][20];

void build(int tl = 0, int tr = maxn, int i = 1){
    if (tl == tr){
        tree[i] = tl; return;
    }
    int tm = (tl + tr) / 2;
    build(tl, tm, i * 2); build(tm + 1, tr, i * 2 + 1);
    tree[i] = (h[tree[i * 2]] < h[tree[i * 2 + 1]] ? 
    tree[i * 2] : tree[i * 2 + 1]);
}

int solve(int s, int e){
    int re = 0;
    for (int p = 19; p >= 0; p--){
        if (jump[s][p] < e) re += (1<<p), s = jump[s][p];
    }
    re++; s = jump[s][0];
    if (s == e) return re;
    return INF;
}

void init(int N, vector<int> H){
    fill(h, h + maxn, INF);
    n = N;
    FOR(i, n) h[i] = H[i];
    build();
    stack<int> s;
    for (int i = n - 1; i >= 0; i--){
        while (!s.empty() && h[s.top()] <= h[i]) s.pop();
        jump[i][0] = (s.empty() ? i : s.top());
        s.push(i);
    }
    for (int p = 1; p < 20; p++){
        FOR(i, n) jump[i][p] = jump[jump[i][p - 1]][p - 1];
    }
}

int minimum_jumps(int a, int b, int c, int d){
    int re = INF;
    for (int i = a; i <= b; i++){
        for (int j = c; j <= d; j++){
            re = min(re, solve(i, j));
        }
    }
    return (re != INF ? re : -1);
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3024 KB Output is correct
2 Correct 3 ms 3028 KB Output is correct
3 Execution timed out 4082 ms 17432 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3072 KB Output is correct
2 Correct 3 ms 3024 KB Output is correct
3 Correct 5 ms 3160 KB Output is correct
4 Correct 3 ms 3088 KB Output is correct
5 Execution timed out 4080 ms 17104 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3068 KB Output is correct
2 Correct 3 ms 3024 KB Output is correct
3 Correct 5 ms 3044 KB Output is correct
4 Incorrect 291 ms 10904 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3068 KB Output is correct
2 Correct 3 ms 3024 KB Output is correct
3 Correct 5 ms 3044 KB Output is correct
4 Incorrect 291 ms 10904 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3024 KB Output is correct
2 Correct 3 ms 3028 KB Output is correct
3 Execution timed out 4082 ms 17432 KB Time limit exceeded
4 Halted 0 ms 0 KB -