#include "jumps.h"
#include <bits/stdc++.h>
#define REP(i,o,n) for(int i=o;i<n;i++)
#define fi first
#define se second
#define pb push_back
using namespace std;
vector<int> h;
vector<int> lm;
vector<int> rm;
int n;
void init(int N, std::vector<int> H) {
h=H;
n=N;
vector<pair<int,int>> stck;
lm.clear(),rm.clear();
REP(i,0,N){
while(stck.size() && stck.back().fi < H[i])stck.pop_back();
lm.pb(-1);
if(stck.size())lm.back() = (stck.back().se);
stck.pb({h[i],i});
}
stck.clear();
REP(ix,0,N){
auto i=N-1-ix;
while(stck.size() && stck.back().fi < H[i])stck.pop_back();
rm.pb(-1);
if(stck.size())rm.back() = (stck.back().se);
stck.pb({h[i],i});
}
reverse(rm.begin(),rm.end());
}
int minimum_jumps(int A, int B, int C, int D) {
int mx=0;
REP(i,C,D+1)mx=max(h[i],mx);
int b=-1;
int roll=-1;
REP(ix,A,B+1){
auto i=A+B-ix;
roll=max(roll,h[i]);
if(roll>mx)break;
if(roll==h[i])b=i;
}
// cerr<<"SELECT "<<b<<endl;
if(b==-1){assert(0);return -1;}
roll=b;
REP(i,1,n+1){
// cerr<<b<<": "<<lm[b]<<", "<<rm[b]<<endl;
if(C <= lm[b] && D <= lm[b])return i;
if(C <= rm[b] && D <= rm[b])return i;
int lc=-1,rc=-1;
if(lm[b]!=-1)lc=h[lm[b]];
if(rm[b]!=-1)rc=h[rm[b]];
if(lc > rc)b=lm[b];
else if(rc > lc)b=rm[b];
else break;
}
REP(i,A,D+1)if(i>mx)return -1;
assert(0);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |