oj.uz

Submission #983855

# Submission time Handle Problem Language Result Execution time Memory
983855 2024-05-16T07:26:30 Z The_Samurai Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 607 ms 4328 KB 
#include "jumps.h"
#include "bits/stdc++.h"
using namespace std;

const int lg = 18, N = 2e5 + 5, inf = 1e9;
vector<int> l(N), r(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();
        r[i] = s.empty() ? n : s.top();
        s.push(i);
    }
    while (!s.empty()) s.pop();
    for (int i = 0; i < n; i++) {
        while (!s.empty() and H[s.top()] < H[i]) s.pop();
        l[i] = s.empty() ? -1 : s.top();
    }
}

int minimum_jumps(int a, int b, int c, int d) {
    return c - b;
    queue<int> q;
    vector<int> ans(n, inf);
    for (int i = a; i <= b; i++) ans[i] = 0, q.push(i);
    while (!q.empty()) {
        int x = q.front(); q.pop();
        if (c <= x and x <= d) return ans[x];
        if (l[x] >= 0 and ans[l[x]] > ans[x] + 1) {
            ans[l[x]] = ans[x] + 1;
            q.push(l[x]);
        }
        if (r[x] < n and ans[r[x]] > ans[x] + 1) {
            ans[r[x]] = ans[x] + 1;
            q.push(r[x]);
        }
    }
    return -1;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Output is correct
2 Correct 1 ms 1880 KB Output is correct
3 Correct 61 ms 4044 KB Output is correct
4 Correct 607 ms 4324 KB Output is correct
5 Correct 494 ms 3176 KB Output is correct
6 Correct 554 ms 4176 KB Output is correct
7 Correct 460 ms 3416 KB Output is correct
8 Correct 570 ms 4328 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Incorrect 1 ms 1880 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Incorrect 1 ms 1880 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Output is correct
2 Correct 1 ms 1880 KB Output is correct
3 Correct 61 ms 4044 KB Output is correct
4 Correct 607 ms 4324 KB Output is correct
5 Correct 494 ms 3176 KB Output is correct
6 Correct 554 ms 4176 KB Output is correct
7 Correct 460 ms 3416 KB Output is correct
8 Correct 570 ms 4328 KB Output is correct
9 Incorrect 1 ms 1880 KB Output isn't correct
10 Halted 0 ms 0 KB -