Submission #1216967

#TimeUsernameProblemLanguageResultExecution timeMemory
1216967tapilyocaRainforest Jumps (APIO21_jumps)C++20
0 / 100
238 ms97036 KiB
#include "jumps.h" #include <bits/stdc++.h> using namespace std; template<typename T> using vec = vector<T>; using ll = long long; #define cerr if(0) cout ll n, l; vec<int> a; vec<vec<ll>> up, upR, upL; void init(int N, std::vector<int> H) { n = N + 2; a = {INT_MAX}; for(int &x : H) a.push_back(x); a.push_back(INT_MAX); up.assign(n,vec<ll>(20,-1)); upR.assign(n,vec<ll>(20,-1)); upL.assign(n,vec<ll>(20,-1)); stack<ll> st; for(int i = 0; i < n; i++) { while(!st.empty() and a[st.top()] <= a[i]) st.pop(); upL[i][0] = (st.empty() ? i : st.top()); st.push(i); } while(!st.empty()) st.pop(); for(int i = n-1; i >= 0; i--) { while(!st.empty() and a[st.top()] <= a[i]) st.pop(); upR[i][0] = (st.empty() ? i : st.top()); st.push(i); } for(ll i = 0; i < n; i++) { up[i][0] = (a[upL[i][0]] > a[upR[i][0]] ? upL[i][0] : upR[i][0]); } for(ll i = 1; i < 20; i++) { for(ll v = 0; v < n; v++) { up[v][i] = up[up[v][i-1]][i-1]; upL[v][i] = upL[upL[v][i-1]][i-1]; upR[v][i] = upR[upR[v][i-1]][i-1]; } } } int minimum_jumps(int A, int B, int C, int D) { ll at = B; A++;B++;C++;D++; // edge case: no middle if(C == B+1) { if(upR[at][0] > D) return -1; return 1; } // find the midpeak ll midPeak = B+1; for(ll i = 19; i >= 0; i--) { if(upR[midPeak][i] < C) { midPeak = upR[midPeak][i]; } } cerr << "Midpeak: " << midPeak << " w/ " << a[midPeak] << endl; // edge case: we are already taller than this if(a[B] >= a[midPeak]) { cerr << "Taller than mid, returning" << endl; if(upR[at][0] > D) return -1; return 1; } // find best starting poll from this for(ll i = 19; i >= 0; i--) { if(upL[at][i] >= A and a[upL[at][i]] < a[midPeak]) { at = upL[at][i]; } } cerr << "New starting poll: " << at << " w/ " << a[at] << endl; // edge case: next best peak brings us right there if(A <= upL[at][0] and upR[ upL[at][0] ][0] <= D and C <= upR[ upL[at][0] ][0]) { cerr << "Oh we can go back one and skip" << endl; return 1; } ll ans = 0; cerr << "Stupid cases done, binlifting to mid" << endl; // binlift us up to mid yay for(ll i = 19; i >= 0; i--) { // cerr << up[at][i] << endl; cerr << "up[" << at << "][" << i << "]:" << up[at][i] << endl; if(a[up[at][i]] <= a[midPeak]) { at = up[at][i]; ans += (1<<i); } } cerr << "After binlift at is " << at << " with " << a[at] << " spent " << ans << endl; if(at == midPeak) { if(upR[at][0] <= D) return ans + 1; return -1; } // if we are NOT at mid check the going left case if(at != midPeak) { cerr << "Not at mid so check left " << endl; if(upL[at][0] > 0 and upR[ upL[at][0] ][0] <= D) return ans + 2; } // going left doesnt work so go right for(int i = 19; i >= 0; i--) { if(upR[at][i] < C) { at = upR[at][i]; ans += (1<<i); } } if(C <= upR[at][0] and upR[at][0] <= D) return ans + 1; 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...