oj.uz

Submission #983816

# Submission time Handle Problem Language Result Execution time Memory
983816 2024-05-16T06:53:34 Z The_Samurai Rainforest Jumps (APIO21_jumps) C++17
0 / 100
 4000 ms 16956 KB 
#include "jumps.h"
#include "bits/stdc++.h"
using namespace std;

const int lg = 18, N = 2e5 + 5, inf = 1e9;
vector jump(lg, vector(N, N));
int n;

void init(int N, vector<int> H) {
    n = N;
    stack<int> s;
    for (int i = n - 1; i >= 0; i--) {
        while (!s.empty() and H[s.top()] < H[i]) s.pop();
        jump[0][i] = s.empty() ? n : s.top();
        s.push(i);
        if (jump[0][i] == n) continue;
        for (int j = 1; j < lg; j++) {
            jump[j][i] = jump[j - 1][jump[j - 1][i]];
            if (jump[j][i] >= n) break;
        }
    }
}

int minimum_jumps(int a, int b, int c, int d) {
    int ans = inf;
    for (int i = a; i <= b; i++) {
        int x = i, now = 0;
        for (int j = lg - 1; j >= 0; j--) {
            if (jump[j][x] >= c) continue;
            x = jump[j][x];
            now += 1 << j;
        }
        if (c <= jump[0][x] and jump[0][x] <= d) ans = min(ans, now + 1);
    }
    if (ans == inf) return -1;
    return ans;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15192 KB Output is correct
2 Correct 7 ms 15288 KB Output is correct
3 Execution timed out 4010 ms 16460 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15192 KB Output is correct
2 Correct 6 ms 15192 KB Output is correct
3 Correct 7 ms 15192 KB Output is correct
4 Correct 7 ms 15156 KB Output is correct
5 Correct 8 ms 15176 KB Output is correct
6 Incorrect 9 ms 15192 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15192 KB Output is correct
2 Correct 6 ms 15192 KB Output is correct
3 Correct 7 ms 15192 KB Output is correct
4 Correct 7 ms 15156 KB Output is correct
5 Correct 8 ms 15176 KB Output is correct
6 Incorrect 9 ms 15192 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15192 KB Output is correct
2 Correct 9 ms 15192 KB Output is correct
3 Correct 7 ms 15192 KB Output is correct
4 Correct 7 ms 15192 KB Output is correct
5 Correct 24 ms 15844 KB Output is correct
6 Correct 34 ms 16128 KB Output is correct
7 Correct 16 ms 15388 KB Output is correct
8 Correct 34 ms 16148 KB Output is correct
9 Correct 11 ms 15192 KB Output is correct
10 Correct 29 ms 16616 KB Output is correct
11 Correct 63 ms 16956 KB Output is correct
12 Correct 57 ms 16736 KB Output is correct
13 Incorrect 47 ms 16740 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15188 KB Output is correct
2 Correct 7 ms 15444 KB Output is correct
3 Correct 6 ms 15192 KB Output is correct
4 Incorrect 129 ms 15344 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15188 KB Output is correct
2 Correct 7 ms 15444 KB Output is correct
3 Correct 6 ms 15192 KB Output is correct
4 Incorrect 129 ms 15344 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15192 KB Output is correct
2 Correct 7 ms 15288 KB Output is correct
3 Execution timed out 4010 ms 16460 KB Time limit exceeded
4 Halted 0 ms 0 KB -