Submission #1197711

#TimeUsernameProblemLanguageResultExecution timeMemory
1197711hengliaoRainforest Jumps (APIO21_jumps)C++20
48 / 100
719 ms130356 KiB
#include "jumps.h" #include<bits/stdc++.h> using namespace std; #define F first #define S second #define pb push_back #define vll vector<ll> #define pll pair<ll, ll> typedef long long ll; namespace{ const ll mxN=2e5+5; const ll LOG=20; ll n; ll h[mxN]; ll id[mxN]; ll rmq1[mxN][LOG]; ll rmq2[mxN][LOG]; ll up1[mxN][LOG]; ll up2[mxN][LOG]; ll rmax(ll a, ll b){ ll lg=31-__builtin_clz(b-a+1); return max(rmq1[a][lg], rmq1[b-(1LL<<lg)+1][lg]); } ll rmin(ll a, ll b){ ll lg=31-__builtin_clz(b-a+1); return min(rmq2[a][lg], rmq2[b-(1LL<<lg)+1][lg]); } ll f1(ll a, ll b, ll val){ ll lef=a, rig=b; ll re=-1; while(lef<=rig){ ll mid=(lef+rig)/2; if(rmax(a, mid)>=val){ re=mid; rig=mid-1; } else{ lef=mid+1; } } return re; } ll f2(ll a, ll b, ll val){ ll lef=a, rig=b; ll re=-1; while(lef<=rig){ ll mid=(lef+rig)/2; if(rmax(mid, b)>=val){ re=mid; lef=mid+1; } else{ rig=mid-1; } } return re; } } void init(int N, std::vector<int> H) { n=N; for(ll i=0;i<n;i++){ h[i]=H[i]-1; id[h[i]]=i; } for(ll i=0;i<n;i++){ rmq1[i][0]=h[i]; rmq2[i][0]=h[i]; } for(ll j=1;j<LOG;j++){ for(ll i=0;i+(1LL<<j)-1<n;i++){ rmq1[i][j]=max(rmq1[i][j-1], rmq1[i+(1LL<<(j-1))][j-1]); rmq2[i][j]=min(rmq2[i][j-1], rmq2[i+(1LL<<(j-1))][j-1]); } } for(ll i=0;i<n;i++){ ll f=f1(i+1, n-1, h[i]); ll s=f2(0, i-1, h[i]); if(f==-1 && s==-1){ up1[i][0]=-1; up2[i][0]=-1; } else if(f==-1){ up1[i][0]=s; up2[i][0]=-1; } else if(s==-1){ up1[i][0]=f; up2[i][0]=-1; } else{ if(h[f]>h[s]){ up1[i][0]=f; up2[i][0]=s; } else{ up1[i][0]=s; up2[i][0]=f; } } // cout<<i<<' '<<up1[i][0]<<' '<<up2[i][0]<<'\n'; } for(ll j=1;j<LOG;j++){ for(ll i=0;i<n;i++){ if(up1[i][j-1]!=-1) up1[i][j]=up1[up1[i][j-1]][j-1]; else up1[i][j]=-1; if(up2[i][j-1]!=-1) up2[i][j]=up2[up2[i][j-1]][j-1]; else up2[i][j]=-1; } } } int minimum_jumps(int A, int B, int C, int D) { ll a=A; ll b=B; ll c=C; ll d=D; ll mx=rmax(c, d); // cout<<"mx: "<<mx<<'\n'; ll tep=f2(0, b, mx); // cout<<"tep: "<<tep<<'\n'; if(tep==b){ return -1; } ll f, s; if(tep==-1){ tep=0; } else{ tep++; } ll mx2=rmax(max(tep, a), b); f=id[mx2]; ll mx3=rmax(tep, c-1); s=f1(c, d, mx3); if(s==-1){ return -1; } ll ans=0; ll cur=f; for(ll i=LOG-1;i>=0;i--){ if(up1[cur][i]==-1) continue; if(h[up1[cur][i]]<=h[s]){ cur=up1[cur][i]; ans+=(1LL<<i); } } for(ll i=LOG-1;i>=0;i--){ if(up2[cur][i]==-1) continue; if(h[up2[cur][i]]<=h[s]){ cur=up2[cur][i]; ans+=(1LL<<i); } } return (int) 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...