Submission #744932

#TimeUsernameProblemLanguageResultExecution timeMemory
744932RushBRainforest Jumps (APIO21_jumps)C++17
0 / 100
4016 ms5664 KiB
#include "jumps.h" #include <bits/stdc++.h> #define FOR(i, a, b) for (int i = (a); i < (b); i++) using namespace std; const int N = 2e5 + 5; int prv[N], nxt[N], n; vector<int> H; void init(int _n, std::vector<int> _H) { n = _n; H.swap(_H); vector<int> st; FOR(i, 0, n) { while (st.size() && H[st.back()] <= H[i]) st.pop_back(); prv[i] = (st.empty() ? -1 : st.back()); st.push_back(i); } st.clear(); for (int i = n - 1; i >= 0; i--) { while (st.size() && H[st.back()] <= H[i]) st.pop_back(); nxt[i] = (st.empty() ? n : st.back()); st.push_back(i); } } int minimum_jumps(int A, int B, int C, int D) { assert(A == B && C == D); int t = 0; while (A != C) { int x = (prv[A] == -1 || H[prv[A]] > H[C] ? -1 : H[prv[A]]), y = (nxt[A] == n || H[nxt[A]] > H[C] ? -1 : H[nxt[A]]); if (x == y && x == -1) return -1; A = (x > y ? prv[A] : nxt[A]); t++; } return t; }
#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...