Submission #1210448

#TimeUsernameProblemLanguageResultExecution timeMemory
1210448badge881Rainforest Jumps (APIO21_jumps)C++20
100 / 100
503 ms50560 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 11; int n; int a[MAXN]; int l[MAXN][20], r[MAXN][20], mx[MAXN][20]; stack<int> s; void init(int N, std::vector<int> H) { n = N; for (int i = 0; i < n; i++) a[i] = H[i]; for (int i = 0; i < n; i++) { while (s.size() && a[s.top()] < a[i]) s.pop(); l[i][0] = (s.empty() ? i : s.top()), s.push(i); } for (int i = n - 1; i >= 0; i--) { while (s.size() && a[s.top()] < a[i]) s.pop(); r[i][0] = (s.empty() ? i : s.top()), s.push(i); } for (int i = 0; i < n; i++) mx[i][0] = (a[l[i][0]] > a[r[i][0]] ? l[i][0] : r[i][0]); for (int k = 1; k < 20; k++) for (int i = 0; i < n; i++) l[i][k] = l[l[i][k - 1]][k - 1], r[i][k] = r[r[i][k - 1]][k - 1], mx[i][k] = mx[mx[i][k - 1]][k - 1]; } int minimum_jumps(int A, int B, int C, int D) { if (r[B][0] > D) return -1; if (r[B][0] >= C) return 1; int p = B + 1; for (int i = 19; i >= 0; i--) if (r[p][i] < C) p = r[p][i]; if (r[p][0] < C || r[p][0] > D) return -1; int s = B, ans = 0; for (int i = 19; i >= 0; i--) if (a[l[s][i]] < a[p] && l[s][i] >= A) s = l[s][i]; if (l[s][0] >= A && C <= r[l[s][0]][0] && r[l[s][0]][0] <= D) return 1; for (int i = 19; i >= 0; i--) if (a[mx[s][i]] <= a[p]) s = mx[s][i], ans += (1 << i); if (s == p) return ans + 1; if (C <= r[s][0] && r[s][0] <= D) return ans + 1; if (C <= r[l[s][0]][0] && r[l[s][0]][0] <= D) return ans + 2; for (int i = 19; i >= 0; i--) if (r[s][i] < C) s = r[s][i], ans += (1 << i); s = r[s][0], ans++; if (C <= s && s <= D) return ans; else return -1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...