제출 #530641

#제출 시각아이디문제언어결과실행 시간메모리
530641czhang2718밀림 점프 (APIO21_jumps)C++17
4 / 100
1524 ms59776 KiB
#include "jumps.h" // #include <bits/stdc++.h> #include <vector> using namespace std; #define rep(i,a,b) for(int i=a; i<=b; i++) #define f first #define s second const int N=200001, LG=18; int lg[N]; int go[N][LG], goleft[N][LG], goright[N][LG]; int mx[N][LG]; int pos[N]; int n; int h[N]; int get_max(int l, int r){ if(r<l) return 0; int len=lg[r-l+1]; return max(mx[l][len], mx[r-(1<<len)+1][len]); } void init(int nn, std::vector<int> H) { n=nn; rep(i,2,n){ lg[i]=lg[i/2]+1; } rep(i,0,n-1){ mx[i][0]=H[i]; pos[H[i]]=i; } rep(j,1,lg[n]){ rep(i,0,n-(1<<j)+1){ mx[i][j]=max(mx[i][j-1], mx[i+(1<<(j-1))][j-1]); } } rep(i,0,n-1){ int ind=i; for(int j=lg[n]; j>=0; j--){ if(ind-(1<<j)>=0 && get_max(ind-(1<<j), i)==H[i]) ind-=(1<<j); } goleft[i][0]=(ind==0?-1:H[ind-1]); } rep(i,0,n-1){ int ind=i; for(int j=lg[n]; j>=0; j--){ if(ind+(1<<j)<n && get_max(i, ind+(1<<j))==H[i]) ind+=(1<<j); } goright[i][0]=(ind==n-1?-1:H[ind+1]); } rep(i,0,n-1){ go[i][0]=max(goleft[i][0], goright[i][0]); } rep(j,1,lg[n]){ rep(i,0,n-1){ goleft[i][j]=(goleft[i][j-1]==-1?-1:goleft[pos[goleft[i][j-1]]][j-1]); goright[i][j]=(goright[i][j-1]==n?n:goright[pos[goright[i][j-1]]][j-1]); go[i][j]=(go[i][j-1]==-1?-1:go[pos[go[i][j-1]]][j-1]); } } } int minimum_jumps(int A, int B, int C, int D) { int mx=get_max(C, D); if(get_max(B, C)>mx) return -1; for(int j=lg[n]; j>=0; j--){ if(A+(1<<j)<=B && get_max(A+(1<<j), B)>mx) A+=(1<<j); } // if(A==B) return -1; if(get_max(A, B)>mx) A++; int ans=0; int a=pos[get_max(A, B)]; int y=get_max(B+1, C-1); for(int j=lg[n]; j>=0; j--){ if(go[a][j]>0 && go[a][j]<=y) ans+=(1<<j), a=pos[go[a][j]]; } if(goright[a][0]!=-1 && pos[goright[a][0]]>=C) return ans+1; if(goleft[a][0]!=-1 && goleft[a][0]<mx && goleft[a][0]>y) return ans+2; for(int j=lg[n]; j>=0; j--){ if(goright[a][j]>0 && pos[goright[a][j]]<C) ans+=(1<<j), a=pos[goright[a][j]]; } return ans+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...