oj.uz

Submission #960840

# Submission time Handle Problem Language Result Execution time Memory
960840 2024-04-11T06:07:57 Z peterandvoi Rainforest Jumps (APIO21_jumps) C++17
0 / 100
 152 ms 46592 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif

const int mxN = (int) 2e5 + 5;
const int LOG = 18;

int N;
int H[mxN], lg[mxN], pos[mxN];
int R[LOG][mxN], B[LOG][mxN], spt[LOG][mxN];

int cmb(int i, int j) {
    return H[i] > H[j] ? i : j;
}

void init(int n, std::vector<int> h) {
    N = n;
    for (int i = 0; i < N; ++i) {
        H[i + 1] = h[i];
        pos[h[i]] = i + 1;
    }
    H[0] = H[n + 1] = n + 1;
    vector<int> st;
    st.emplace_back(n + 1);
    for (int i = n; i >= 1; --i) {
        while (st.size() && H[i] >= H[st.back()]) {
            st.pop_back();
        }
        R[0][i] = st.back();
    }
    while (st.size()) {
        st.pop_back();
    }
    st.emplace_back(0);
    for (int i = 1; i <= n; ++i) {
        while (st.size() && H[i] >= H[st.back()]) {
            st.pop_back();
        }
        if (i > 1) {
            lg[i] = lg[i / 2] + 1;
        }
        spt[0][i] = H[i];
        B[0][i] = cmb(R[0][i], st.back());
    }
    for (int i = 1; i <= lg[n]; ++i) {
        for (int j = 1; j <= n; ++j) {
            B[i][j] = B[i - 1][B[i - 1][j]];
            R[i][j] = R[i - 1][R[i - 1][j]];
            if (j + (1 << i) - 1 <= n) {
                spt[i][j] = max(spt[i - 1][j], spt[i - 1][j + (1 << (i - 1))]);
            }
        }
    }
}

int get(int l, int r) {
    int k = lg[r - l + 1];
    return max(spt[k][l], spt[k][r - (1 << k) + 1]);
}

int minimum_jumps(int a, int b, int c, int d) {
    a++, b++, c++, d++;
    int l = a, r = b, s = -1;
    int Hr = get(c, d);
    while (l <= r) {
        int mid = l + r >> 1;
        int Hl = get(mid, b);
        if (Hl < Hr) {
            s = pos[Hl];
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    if (s == -1) {
        return -1;
    }
    if (b + 1 == c) {
        return 1;
    }
    int Hmid = get(b + 1, c - 1);
    if (H[s] > Hmid) {
        return 1;
    }
    if (Hmid > Hr) {
        return -1;
    }
    int res = 0;
    for (int i = lg[N]; i >= 0; --i) {
        if (H[B[i][s]] < Hmid) {
            s = B[i][s];
            res += 1 << i;
        }
    }
    if (H[B[0][s]] < Hr) {
        return res + 2;
    }
    for (int i = lg[N]; i >= 0; --i) {
        if (H[R[i][s]] < Hmid) {
            s = R[i][s];
            res += 1 << i;
        }
    }
    return res + 2;
}

#ifdef ngu
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
    int n;
    cin >> n;
    vector<int> h(n);
    for (int i = 0; i < n; ++i) {
        cin >> h[i];
    }
    init(n, h);
    int q;
    cin >> q;
    while (q--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        cout << minimum_jumps(a, b, c, d) << "\n";
    }
}
#endif

Compilation message

jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:72:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
0 / 4.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Correct 2 ms 12628 KB Output is correct
4 Correct 2 ms 12632 KB Output is correct
5 Correct 23 ms 45912 KB Output is correct
6 Correct 28 ms 46592 KB Output is correct
7 Correct 16 ms 44876 KB Output is correct
8 Correct 29 ms 46544 KB Output is correct
9 Correct 8 ms 43864 KB Output is correct
10 Correct 33 ms 46560 KB Output is correct
11 Incorrect 36 ms 46416 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

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

Subtask #6
0 / 21.0

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

Subtask #7
0 / 19.0

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