Submission #740757

#	Time	Username	Problem	Language	Result	Execution time	Memory
740757		nguyentunglam	Rainforest Jumps (APIO21_jumps)	C++17	8 / 100	4059 ms	5860 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];

void init(int n, vector<int> H) {
    stack<int> st;
    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]);
    }
}

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) {
    int ret = 1e9;
    for(int i = a; i <= b; i++) for(int j = c; j <= d; j++) {
        ret = min(ret, get(i, j));
    }
    if (ret == 1e9) return -1;
    return ret;
}

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

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