제출 #1097988

#제출 시각아이디문제언어결과실행 시간메모리
1097988PieArmy밀림 점프 (APIO21_jumps)C++17
100 / 100
966 ms60040 KiB
#include "jumps.h" typedef long long ll; ll pie(ll army){return (1ll<<army);} #include <bits/stdc++.h> #define fr first #define sc second #define pb push_back #define endl '\n' #define mid ((left+right)>>1) const ll inf=2000000000000000005; const int sonsuz=2000000005; using namespace std; ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;} int n; int lef[200002][18],rig[200002][18],smart[200002][18][2]; int cal(int pos,int C,int D){ int ans=0; int mn=pos,mx=pos; for(int i=18-1;i>=0;i--){ if(max(smart[mx][i][1],smart[mn][i][1])>=C)continue; ans+=pie(i); int tmp; tmp=min(smart[mx][i][0],smart[mn][i][0]); mx=max(smart[mx][i][1],smart[mn][i][1]); mn=tmp; } if((smart[mx][0][1]>=C&&smart[mx][0][1]<=D)||(smart[mn][0][1]>=C&&smart[mn][0][1]<=D))return ans+1; for(int i=18-1;i>=0;i--){ if(rig[mx][i]>=C)continue; ans+=pie(i); mx=rig[mx][i]; } mx=rig[mx][0]; if(mx>=C&&mx<=D)return ans+1; return -1; } int minimum_jumps(int A,int B,int C,int D){ A++;B++;C++;D++; int ans=cal(B,C,D); if(ans==-1)return ans; int pos=B; for(int i=18-1;i>=0;i--){ if(lef[pos][i]<A)continue; int res=cal(lef[pos][i],C,D); if(res==-1)continue; pos=lef[pos][i]; ans=res; } return ans; } void init(int N,vector<int> H){ n=N; int arr[n+2]; for(int i=1;i<=n;i++){ arr[i]=H[i-1]; } vector<int>sta; for(int i=1;i<=n;i++){ while(sta.size()&&arr[sta.back()]<arr[i])sta.pop_back(); if(sta.size()==0)lef[i][0]=i; else lef[i][0]=sta.back(); sta.pb(i); } while(sta.size())sta.pop_back(); for(int i=n;i>=1;i--){ while(sta.size()&&arr[sta.back()]<arr[i])sta.pop_back(); if(sta.size()==0)rig[i][0]=i; else rig[i][0]=sta.back(); sta.pb(i); } for(int i=1;i<18;i++){ for(int j=1;j<=n;j++){ lef[j][i]=lef[lef[j][i-1]][i-1]; rig[j][i]=rig[rig[j][i-1]][i-1]; } } for(int i=1;i<=n;i++){ smart[i][0][0]=lef[i][0]; smart[i][0][1]=rig[i][0]; } for(int i=1;i<18;i++){ for(int j=1;j<=n;j++){ smart[j][i][0]=min(smart[smart[j][i-1][0]][i-1][0],smart[smart[j][i-1][1]][i-1][0]); smart[j][i][1]=max(smart[smart[j][i-1][0]][i-1][1],smart[smart[j][i-1][1]][i-1][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...