Submission #1197007

#TimeUsernameProblemLanguageResultExecution timeMemory
1197007NoMercyRainforest Jumps (APIO21_jumps)C++20
77 / 100
4094 ms50492 KiB
#include "jumps.h" #include <bits/stdc++.h> using namespace std; const int lg = 20, MAXN = 2e5 + 55; int up[lg][MAXN][3], N, H[MAXN]; void init(int n, vector<int> h) { N = n; H[0] = H[N + 1] = 1e9 + 7; for (int i = 1;i <= N;i ++) H[i] = h[i - 1]; N += 2; stack<int> st; for (int i = 0; i < N; ++i) { while (!st.empty() && H[st.top()] <= H[i]) st.pop(); if (st.size() > 0) up[0][i][0] = st.top(); else up[0][i][0] = i; 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(); if (st.size() > 0) up[0][i][1] = st.top(); else up[0][i][1] = i; st.push(i); } for (int i = 0; i < N; ++i) { up[0][i][2] = H[up[0][i][0]] > H[up[0][i][1]] ? up[0][i][0] : up[0][i][1]; } for (int bt = 1;bt < lg;bt ++) { for (int i = 0;i < N;i ++) { up[bt][i][0] = up[bt - 1][up[bt - 1][i][0]][0]; up[bt][i][1] = up[bt - 1][up[bt - 1][i][1]][1]; up[bt][i][2] = up[bt - 1][up[bt - 1][i][2]][2]; } } } int minimum_jumps(int A, int B, int C, int D) { A ++; B ++; C ++; D ++; int res = 1e9 + 7; for (int ind = C;ind <= D;ind ++) { int _B = B; for (int bt = lg - 1;bt >= 0;bt --) { if (A <= up[bt][B][0] && H[up[bt][B][0]] < H[ind]) { B = up[bt][B][0]; } } int cnt = 0; for (int bt = lg - 1;bt >= 0;bt --) { if (H[up[bt][B][2]] <= H[ind]) { B = up[bt][B][2]; cnt += (1 << bt); } } if (H[up[0][B][0]] > H[ind]) { for (int bt = lg - 1;bt >= 0;bt --) { if (H[up[bt][B][1]] <= H[ind]) { B = up[bt][B][1]; cnt += (1 << bt); } } } else { for (int bt = lg - 1;bt >= 0;bt --) { if (H[up[bt][B][0]] <= H[ind]) { B = up[bt][B][0]; cnt += (1 << bt); } } } if (ind == B) { res = min(res, cnt); } B = _B; } if (res == 1e9 + 7) return -1; return res; }
#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...