oj.uz

Submission #415861

# Submission time Handle Problem Language Result Execution time Memory
415861 2021-06-01T15:55:11 Z valerikk Rainforest Jumps (APIO21_jumps) C++17
0 / 100
 4000 ms 5812 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 7;

int n, h[N];
int l[N], r[N], m[N];

void init(int nn, vector<int> hh) {
    for (int i = 0; i < nn; i++) h[i + 1] = hh[i] - 1;
    h[0] = nn;
    h[nn + 1] = nn + 1;
    n = nn + 2;
    vector<int> st;
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && h[st.back()] < h[i]) {
            r[st.back()] = i;
            st.pop_back();
        }
        st.push_back(i);
    }
    r[n - 1] = n - 1;
    st.clear();
    for (int i = n - 1; i >= 0; --i) {
        while (!st.empty() && h[st.back()] < h[i]) {
            l[st.back()] = i;
            st.pop_back();
        }
        st.push_back(i);
    }
    l[0] = 0;
    st.clear();
    for (int i = 0; i < n; ++i) m[i] = h[l[i]] > h[r[i]] ? l[i] : r[i];
}

int minimum_jumps(int aa, int bb, int cc, int dd) {
    int a = aa + 1, b = bb + 1, c = cc + 1, d = dd + 1;
    int mx = 0;
    for (int i = c; i <= d; ++i) mx = max(mx, h[i]);
    int mx1  = -1e9;
    for (int i = b + 1; i < c; ++i) mx1 = max(mx1, h[i]);
    if (mx1 > mx || h[b] > mx) return -1;
    int st = b;
    for (int i = a; i <= b; ++i) {
        if (h[i] < mx && h[i] > h[st]) st = i;
    }
    int res = 1;
    while (h[st] < mx1) {
        ++res;
        if (h[m[st]] < h[mx]) st = m[st]; else st = r[st];
    }
    return res;
}

#ifdef LOCAL

int main() {
    freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int nn, qq;
    cin >> nn >> qq;
    vector<int> hh(nn);
    for (auto &x : hh) cin >> x;
    init(nn, hh);
    while (qq--) {
        int aa, bb, cc, dd;
        cin >> aa >> bb >> cc >> dd;
        cout << minimum_jumps(aa, bb, cc, dd) << endl;
    }
    return 0;
}

#endif

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 2496 ms 4704 KB Output is correct
4 Execution timed out 4067 ms 5812 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 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Incorrect 4 ms 200 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 28 ms 4032 KB Output is correct
6 Correct 34 ms 4884 KB Output is correct
7 Correct 17 ms 2624 KB Output is correct
8 Correct 48 ms 4904 KB Output is correct
9 Correct 6 ms 968 KB Output is correct
10 Correct 34 ms 4916 KB Output is correct
11 Correct 31 ms 5812 KB Output is correct
12 Correct 30 ms 5648 KB Output is correct
13 Correct 30 ms 5556 KB Output is correct
14 Correct 48 ms 4928 KB Output is correct
15 Correct 30 ms 5432 KB Output is correct
16 Correct 30 ms 5776 KB Output is correct
17 Incorrect 29 ms 5772 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Incorrect 889 ms 2324 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 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Incorrect 889 ms 2324 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 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 2496 ms 4704 KB Output is correct
4 Execution timed out 4067 ms 5812 KB Time limit exceeded
5 Halted 0 ms 0 KB -