Submission #740768

#	Time	Username	Problem	Language	Result	Execution time	Memory
740768		nguyentunglam	Rainforest Jumps (APIO21_jumps)	C++17	21 / 100	994 ms	6052 KiB

jumps

#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;
const int N = 1e5 + 10;
int l[N], r[N], h[N];
int n ;

void init(int _n, vector<int> H) {
    stack<int> st;
    n = _n;
    for(int i = 0; i < n; i++) h[i] = H[i]; h[n] = 1e9;
    for(int i = 0; i < n; i++) {
        while (!st.empty() && h[st.top()] < h[i]) st.pop();
        l[i] = st.empty() ? n : st.top();
        st.push(i);
    }
    while (!st.empty()) st.pop();
    for(int i = n - 1; i >= 0; i--) {
        while (!st.empty() && h[st.top()] < h[i]) st.pop();
        r[i] = st.empty() ? n : st.top();
        st.push(i);
        if (h[l[i]] > h[r[i]]) swap(l[i], r[i]);
    }
    h[n + 1] = 0;
}

int get(int from, int to) {
    int ret = 0;
    while (h[r[from]] <= h[to]) ret++, from = r[from];
    while (h[l[from]] <= h[to]) ret++, from = l[from];
    if (from == to) return ret;
    return 1e9;
}

int minimum_jumps(int a, int b, int c, int d) {
    if (max(a, c) <= min(b, d)) return 0;
    int ret = 0, mx = 0, last = a;
    for(int j = c; j <= d; j++) mx = max(mx, h[j]);
    for(int i = a; i <= b; i++) if (h[i] > mx) last = i + 1;
    int idx = last;
    if (idx > b) return -1;
    for(int j = last + 1; j <= b; j++) {
        if (h[j] > h[idx]) idx = j;
    }
    int block = n + 1;
    for(int i = b + 1; i <= c - 1; i++) if (h[i] > h[block]) block = i;
    if (!(h[idx] < mx && h[block] < mx)) return -1;
    while (h[r[idx]] < h[block]) ret++, idx = r[idx];
//    cout << idx << " " << block << " " << r[idx] << " " << mx << " " << ret << endl;
    if (h[idx] > h[block]) return ret + 1;
    if (h[r[idx]] < mx) return ret + 2;
    return ret + get(idx, block) + 1;
}

#ifdef ngu
int main() {
    if (fopen ("task.inp", "r")) {
        freopen ("task.inp", "r", stdin);
        freopen ("task.out", "w", stdout);
    }
    int n; cin >> n;
    vector<int> h;
    h.resize(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) << endl;
    }
}
#endif // ngu

Compilation message (stderr)

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:14:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   14 |     for(int i = 0; i < n; i++) h[i] = H[i]; h[n] = 1e9;
      |     ^~~
jumps.cpp:14:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   14 |     for(int i = 0; i < n; i++) h[i] = H[i]; h[n] = 1e9;
      |                                             ^

• Subtask 1: 0 / 4
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19