oj.uz

Submission #415859

# Submission time Handle Problem Language Result Execution time Memory
415859 2021-06-01T15:53:58 Z valerikk Rainforest Jumps (APIO21_jumps) C++17
0 / 100
 4000 ms 5892 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 = a;
    for (int i = a; i <= b; ++i) {
        if (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 2387 ms 4736 KB Output is correct
4 Execution timed out 4005 ms 5776 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 2 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 2 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 36 ms 3988 KB Output is correct
6 Correct 50 ms 4896 KB Output is correct
7 Correct 17 ms 2624 KB Output is correct
8 Correct 36 ms 4924 KB Output is correct
9 Correct 9 ms 1024 KB Output is correct
10 Correct 34 ms 4908 KB Output is correct
11 Correct 49 ms 5892 KB Output is correct
12 Incorrect 45 ms 5684 KB Output isn't correct
13 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 2 ms 200 KB Output is correct
4 Incorrect 1022 ms 2368 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 2 ms 200 KB Output is correct
4 Incorrect 1022 ms 2368 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 2387 ms 4736 KB Output is correct
4 Execution timed out 4005 ms 5776 KB Time limit exceeded
5 Halted 0 ms 0 KB -