제출 #485940

#제출 시각아이디문제언어결과실행 시간메모리
485940MOUF_MAHMALAT밀림 점프 (APIO21_jumps)C++14
4 / 100
1189 ms44948 KiB
#include "jumps.h" #include<bits/stdc++.h> using namespace std; typedef int ll; stack<ll>st; ll n,l[18][200009],r[18][200009]; ll u[18][200009]; void init(int N, vector<int>h) { n=N; for(ll i=0; i<n; i++) { while(!st.empty()&&h[st.top()]<h[i]) st.pop(); if(st.empty()) l[0][i]=-1; else l[0][i]=st.top(); st.push(i); } while(!st.empty()) st.pop(); for(ll i=n-1; i>=0; i--) { while(!st.empty()&&h[st.top()]<h[i]) st.pop(); if(st.empty()) r[0][i]=-1; else r[0][i]=st.top(); st.push(i); } for(ll i=0; i<n; i++) { if(l[0][i]==-1) u[0][i]=r[0][i]; else if(r[0][i]==-1) u[0][i]=l[0][i]; else if(h[l[0][i]]<h[r[0][i]]) u[0][i]=r[0][i]; else u[0][i]=l[0][i]; } for(ll i=1; i<18; i++) for(ll j=0; j<n; j++) { if(l[i-1][j]!=-1) l[i][j]=l[i-1][l[i-1][j]]; else l[i][j]=-1; if(r[i-1][j]!=-1) r[i][j]=r[i-1][r[i-1][j]]; else r[i][j]=-1; if(u[i-1][j]!=-1) u[i][j]=u[i-1][u[i-1][j]]; else u[i][j]=-1; } } int minimum_jumps(ll a,ll b,ll c,ll d) { ll s=b,ans=0; for(ll i=17; i>=0; i--) if(l[i][s]>=a&&r[0][l[i][s]]!=-1&&r[0][l[i][s]]<=d) s=l[i][s]; for(ll i=17; i>=0; i--) if(u[i][s]!=-1&&u[i][s]<c&&r[0][u[i][s]]!=-1&&r[0][u[i][s]]<=d) s=u[i][s],ans+=(1<<i); for(ll i=17; i>=0; i--) if(r[i][s]!=-1&&r[i][s]<c&&r[0][r[i][s]]!=-1&&r[0][r[i][s]]<=d) s=r[i][s],ans+=(1<<i); if(r[0][s]>d||r[0][s]==-1) return -1; 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...