Submission #916256

#TimeUsernameProblemLanguageResultExecution timeMemory
916256adhityamvRainforest Jumps (APIO21_jumps)C++17
23 / 100
4046 ms83356 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define mp make_pair #define pii pair<int,int> #define fi first #define se second const int N=200000; const int ln=20; int n; vector<int> seg[4*N]; int big[N][ln]; int small[N][ln]; int l[N]; int r[N]; int h[N]; int ind[N+1]; void Build(int l,int r,int pos){ if(l==r){ seg[pos].push_back(h[l]); return; } int m=(l+r)/2; Build(l,m,2*pos); Build(m+1,r,2*pos+1); merge(seg[2*pos].begin(),seg[2*pos].end(),seg[2*pos+1].begin(),seg[2*pos+1].end(),back_inserter(seg[pos])); } int Query(int l,int r,int pos,int ql,int qr,int ub){ if(ql>r || qr<l) return -1; if(ql<=l && qr>=r){ auto it=lower_bound(seg[pos].begin(),seg[pos].end(),ub); if(it==seg[pos].begin()) return -1; it--; return (*it); } int m=(l+r)/2; return max(Query(l,m,2*pos,ql,qr,ub),Query(m+1,r,2*pos+1,ql,qr,ub)); } void init(int nn,vector<int> hh){ n=nn; for(int i=0;i<n;i++) h[i]=hh[i];; for(int i=0;i<n;i++) ind[h[i]]=i; stack<int> fl; fl.push(-1); for(int i=0;i<n;i++){ while(fl.top()!=-1 && h[fl.top()]<h[i]) fl.pop(); l[i]=fl.top(); fl.push(i); } stack<int> fr; fr.push(-1); for(int i=n-1;i>=0;i--){ while(fr.top()!=-1 && h[fr.top()]<h[i]) fr.pop(); r[i]=fr.top(); fr.push(i); } for(int i=0;i<n;i++){ if(l[i]==-1){ big[i][0]=small[i][0]=r[i]; continue; } if(r[i]==-1){ big[i][0]=small[i][0]=l[i]; continue; } if(h[l[i]]>h[r[i]]){ big[i][0]=l[i]; small[i][0]=r[i]; } else{ big[i][0]=r[i]; small[i][0]=l[i]; } } for(int j=1;j<ln;j++){ for(int i=0;i<n;i++){ if(big[i][j-1]==-1) big[i][j]=-1; else big[i][j]=big[big[i][j-1]][j-1]; if(small[i][j-1]==-1) small[i][j]=-1; else small[i][j]=small[small[i][j-1]][j-1]; } } Build(0,n-1,1); } int check(int s,int e){ if(h[s]>=h[e]) return -1; int ans=0; for(int j=ln-1;j>=0;j--){ if(big[s][j]!=-1 && h[big[s][j]]<h[e]){ s=big[s][j]; ans+=(1<<j); } } if(e==l[s] || e==r[s]) return ans+1; for(int j=ln-1;j>=0;j--){ if(small[s][j]!=-1 && h[small[s][j]]<h[e]){ s=small[s][j]; ans+=(1<<j); } } if(e==l[s] || e==r[s]) return ans+1; return -1; } int minimum_jumps(int a,int b,int c,int d){ int ans=N; for(int j=c;j<=d;j++){ int s=ind[Query(0,n-1,1,a,b,h[j])]; int cans=check(s,j); if(cans!=-1) ans=min(cans,ans); } if(ans==N) ans=-1; return ans; }
#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...