Submission #925160

#	Time	Username	Problem	Language	Result	Execution time	Memory
925160		TAhmed33	Rainforest Jumps (APIO21_jumps)	C++17	0 / 100	192 ms	11552 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 25;
int a[MAXN], prv[MAXN], nxt[MAXN], n;
int dp[MAXN][19], dp2[MAXN][19], dp3[MAXN][19];
void init (int N, vector <int> h) {
	n = N;
	for (int i = 0; i < n; i++) a[i + 1] = h[i];
	stack <int> cur;
	cur.push(1);
	for (int i = 2; i <= n; i++) {
		while (!cur.empty() && a[i] > a[cur.top()]) {
			nxt[cur.top()] = i;
			cur.pop();
		}
		cur.push(i);
	}
	while (!cur.empty()) {
		nxt[cur.top()] = 0;
		cur.pop();
	}
	cur.push(n);
	for (int i = n - 1; i >= 1; i--) {
		while (!cur.empty() && a[i] > a[cur.top()]) {
			prv[cur.top()] = i;
			cur.pop();
		}
		cur.push(i);
	}
	while (!cur.empty()) {
		prv[cur.top()] = 0;
		cur.pop();
	}
    for (int i = 1; i <= n; i++) {
        dp2[0][i] = prv[i];
        dp3[0][i] = nxt[i];
        if (prv[i] && nxt[i] && a[prv[i]] > a[nxt[i]]) {
            dp[0][i] = prv[i];
        } else if (prv[i] && nxt[i] && a[prv[i]] < a[nxt[i]]) {
            dp[0][i] = nxt[i];
        }
    }
    for (int i = 1; i < 19; i++) {
        for (int j = 1; j <= n; j++) {
            dp2[i][j] = dp2[i - 1][dp2[i - 1][j]];
            dp3[i][j] = dp3[i - 1][dp3[i - 1][j]];
            dp[i][j] = dp[i - 1][dp[i - 1][j]];
        }
    }
}
int jump (int a, int b) {
    for (int i = 18; i >= 0; i--) {
        if (b & (1 << i)) {
            a = dp[i][a];
        }
    }
    return a;
}
int jump2 (int a, int b) {
    for (int i = 18; i >= 0; i--) {
        if (b & (1 << i)) {
            a = dp2[i][a];
        }
    }
    return a;
}
int jump3 (int a, int b) {
    for (int i = 18; i >= 0; i--) {
        if (b & (1 << i)) {
            a = dp3[i][a];
        }
    }
    return a;
}
int minimum_jumps (int a, int b, int c, int d) {
    a++; b++; c++; d++;
    int l = 0, r = n, ans = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        int x = jump2(b, mid);
        if (x == 0 || x < a) {
            r = mid - 1; continue;
        }
        if (!nxt[x] || nxt[x] > d) {
            r = mid - 1; continue;
        }
        l = mid + 1; ans = mid;
    }
    if (ans == -1) return -1;
    int cur = jump2(b, ans);
    //cout << cur << '\n';
    l = 1, r = n; int ans2 = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        int x = jump(cur, mid);
        if (x == 0) {
            r = mid - 1; continue;
        }
       // cout << mid << " n\n";
        if (x > c) {
            r = mid - 1; continue;
        }
        if (!nxt[x] || !prv[x] || nxt[x] > d) {
            r = mid - 1; continue;
        }
        l = mid + 1; ans2 = mid;
    }
    int cur2 = jump(cur, ans2);
  // cout << cur2 << '\n'; //cout << ans2 << '\n';
    l = 0, r = n; int ans3 = -1;
   // cout << nxt[cur2] << '\n';
   // cout << nxt[nxt[cur2]] << '\n';
   // cout << nxt[nxt[nxt[cur2]]] << '\n';
    while (l <= r) {
        int mid = (l + r) >> 1;
        int x = jump3(cur2, mid);
       // cout << x << " | " << mid << '\n';
        if (!x || x >= c) {
            r = mid - 1; ans3 = mid;
        } else {
            l = mid + 1;
        }
    }
    //cout << ans3 << '\n';
    if (ans3 == -1) return -1;
    int cur3 = jump3(cur2, ans3);
    if (!cur3) return -1;
    //cout << cur3 << '\n';
    if (cur3 > d) return -1;
    return ans2 + ans3;
}/*
int main () {
    int n, q; cin >> n >> q; vector <int> h(n); for (auto &i : h) cin >> i;
    init(n, h);
    while (q--) {
        int a, b, c, d; cin >> a >> b >> c >> d;
        cout << minimum_jumps(a, b, c, d) << '\n';
    }
}*/

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