Submission #740754

#	Time	Username	Problem	Language	Result	Execution time	Memory
740754		nguyentunglam	Rainforest Jumps (APIO21_jumps)	C++17	8 / 100	4051 ms	5948 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], d[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]);
    }

}

int get(int from, int to) {
    int ret = 0;
    for(int i = 0; i < n; i++) d[i] = 0;
    d[from] = 1;
    queue<int> q; q.push(from);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (u == to) return d[u] - 1;
        if (!d[l[u]]) d[l[u]] = d[u] + 1, q.push(l[u]);
        if (!d[r[u]]) d[r[u]] = d[u] + 1, q.push(r[u]);
    }
    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: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;
      |                                             ^
jumps.cpp: In function 'int get(int, int)':
jumps.cpp:31:9: warning: unused variable 'ret' [-Wunused-variable]
   31 |     int ret = 0;
      |         ^~~

• 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