This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ar array
#define vo vector
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (ll)(x).size()
#define rep(i, a, b) for(ll i=a; i<b; i++)
#define repd(i, a, b) for(ll i=a; i>=b; i--)
int n, h[int(2e5+10)];
int jmp_l[int(2e5+10)][30];
int jmp_r[int(2e5+10)][30];
void init(int N, vo<int> H) {
n=N+2;
h[0]=1e8;
rep(i, 0, N)
h[i+1]=H[i];
h[n-1]=1e8;
stack<int> st;
rep(i, 0, n) {
while(sz(st) && h[st.top()]<h[i])
jmp_r[st.top()][0]=i, st.pop();
st.push(i);
}
while(sz(st))
st.pop();
repd(i, n-1, 0) {
while(sz(st) && h[st.top()]<h[i])
jmp_l[st.top()][0]=i, st.pop();
st.push(i);
}
rep(i, 1, 30)
rep(k, 0, n) {
jmp_l[k][i]=jmp_l[jmp_l[k][i-1]][i-1];
jmp_r[k][i]=jmp_r[jmp_r[k][i-1]][i-1];
}
}
int minimum_jumps(int A, int B, int C, int D) {
A++, B++, C++, D++;
if(B+1==C) {
if(jmp_r[B][0]>D)
return -1;
else
return 1;
}
int ind=B+1;
repd(i, 29, 0)
if(jmp_r[ind][i]<C)
ind=jmp_r[ind][i];
if(h[B]>h[ind]) {
if(jmp_r[B][0]>D)
return -1;
else
return 1;
}
int cur=B;
repd(i, 29, 0)
if(h[jmp_l[cur][i]]<h[ind] && jmp_l[cur][i]>=A)
cur=jmp_l[cur][i];
int ans=0;
if(jmp_l[cur][0]>=A) {
if(jmp_r[jmp_l[cur][0]][0]<=D)
return 1;
}
else {
repd(i, 29, 0) {
if(h[jmp_l[cur][i]]>=h[jmp_r[cur][i]] && h[jmp_l[cur][i]]<=h[ind]) {
ans|=(1<<i);
cur=jmp_l[cur][i];
continue;
}
if(h[jmp_r[cur][i]]>=h[jmp_l[cur][i]] && h[jmp_r[cur][i]]<=h[ind]) {
ans|=(1<<i);
cur=jmp_r[cur][i];
}
}
if(h[cur]==h[ind])
return ans+1;
if(jmp_l[cur][0] && jmp_r[jmp_l[cur][0]][0]<=D)
return ans+2;
}
repd(i, 29, 0)
if(jmp_r[cur][i]<C) {
cur=jmp_r[cur][i];
ans+=1<<i;
}
if(jmp_r[cur][0]>=C && jmp_r[cur][0]<=D)
return ans+1;
else
return -1;
}
# | 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... |