Submission #1203251

#TimeUsernameProblemLanguageResultExecution timeMemory
1203251Francisco_MartinRainforest Jumps (APIO21_jumps)C++20
4 / 100
460 ms98440 KiB
#include "jumps.h" #include <bits/stdc++.h> using namespace std; using ll=long long; ll N; const ll INF=1e9; vector<int> H; vector<vector<ll>> L, R, hi; void init(int N_,vector<int> H_){ H=H_; H.insert(H.begin(),INF); H.insert(H.end(),INF); N=N_+2; L=R=hi=vector<vector<ll>>(20,vector<ll>(N)); stack<ll> stk, stk2; for(int i=0; i<N; i++){ while(!stk.empty() && H[stk.top()]<=H[i]) stk.pop(); if(stk.empty()) L[0][i]=i; else L[0][i]=stk.top(); stk.push(i); } for(int i=N-1; i>=0; i--){ while(!stk2.empty() && H[stk2.top()]<=H[i]) stk2.pop(); if(stk2.empty()) R[0][i]=i; else R[0][i]=stk2.top(); stk2.push(i); } for(int i=0; i<N; i++){ if(H[L[0][i]]>H[R[0][i]]) hi[0][i]=L[0][i]; else hi[0][i]=R[0][i]; } for(int i=1; i<20; i++){ for(int j=0; j<N; j++){ L[i][j]=L[i-1][L[i-1][j]]; R[i][j]=R[i-1][R[i-1][j]]; hi[i][j]=hi[i-1][hi[i-1][j]]; } } } int minimum_jumps(int A,int B,int C,int D) { ll ans=0; A++; B++; C++; D++; auto query=[&](ll l,ll r){ for(int i=19; i>=0; i--){ if(R[i][l]<=r) l=R[i][l]; } return l; }; if(B==C-1){ if(R[0][B]<=D) return 1; else return -1; } ll x=query(B+1,C-1); if(H[B]>H[x]){ if(R[0][B]<=D) return 1; else return -1; } for(int i=19; i>=0; i--){ if(A<=L[i][B] && H[L[i][B]]<H[x]) B=L[i][B]; } if(A<=L[0][B]){ if(R[0][L[0][B]]<=D) return 1; }else{ for(int i=19; i>=0; i--){ if(H[hi[i][B]]<=H[x]){ ans|=(1<<i); B=hi[i][B]; } } if(B==x){ if(R[0][B]<=D) return ans+1; else return -1; } if(0<L[0][B] && R[0][L[0][B]]<=D) return ans+2; } ans=0; for(int i=19; i>=0; i--){ if(R[i][B]<C){ ans+=(1<<i); B=R[i][B]; } } if(C<=R[0][B] && R[0][B]<=D) return ans+1; 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...