제출 #1266310

#제출 시각아이디문제언어결과실행 시간메모리
1266310PlayVoltzRainforest Jumps (APIO21_jumps)C++20
100 / 100
583 ms74820 KiB
#include "jumps.h" #include <bits/stdc++.h> using namespace std; vector<int> h; vector<vector<int> > twokr, twok, twokl; void init(int n, vector<int> H){ h.resize(n+2, INT_MAX/2); for (int i=0; i<n; ++i)h[i+1]=H[i]; vector<int> l(n+2), r(n+2); stack<int> st; st.push(0); for (int i=1; i<=n+1; ++i){ while (h[st.top()]<h[i])r[st.top()]=i, st.pop(); l[i]=st.top(); st.push(i); } twok.resize(n+2, vector<int>(20)); twokl.resize(n+2, vector<int>(20)); twokr.resize(n+2, vector<int>(20)); twok[0][0]=0; twok[n+1][0]=n+1; twokr[n+1][0]=n+1; twokl[0][0]=0; for (int i=1; i<=n; ++i){ twokr[i][0]=r[i]; twokl[i][0]=l[i]; if (h[l[i]]>h[r[i]])twok[i][0]=l[i]; else twok[i][0]=r[i]; } for (int j=1; j<20; ++j)for (int i=0; i<=n+1; ++i)twok[i][j]=twok[twok[i][j-1]][j-1], twokr[i][j]=twokr[twokr[i][j-1]][j-1], twokl[i][j]=twokl[twokl[i][j-1]][j-1]; } int minimum_jumps(int A, int B, int C, int D){ int a=A+1, b=B+1, c=C+1, d=D+1, node=b, mx=b+1, ans=0; if (b+1==c)return (twokr[b][0]<=d?1:-1); for (int i=19; i>=0; --i)if (twokr[mx][i]<=c-1)mx=twokr[mx][i]; if (h[b]>h[mx])return (twokr[b][0]<=d?1:-1); for (int i=19; i>=0; --i)if (twokl[node][i]>=a&&h[twokl[node][i]]<h[mx])node=twokl[node][i]; if (twokl[node][0]>=a&&twokr[twokl[node][0]][0]<=d)return 1; if (twokl[node][0]<a){ for (int i=19; i>=0; --i)if (h[twok[node][i]]<=h[mx])node=twok[node][i], ans+=(1<<i); if (node==mx)return (twokr[node][0]<=d?ans+1:-1); if (c<=twokr[node][0]&&twokr[node][0]<=d)return ans+1; if (twokl[node][0]&&c<=twokr[twokl[node][0]][0]&&twokr[twokl[node][0]][0]<=d)return ans+2; } for (int i=19; i>=0; --i)if (twokr[node][i]<c)node=twokr[node][i], ans+=(1<<i); if (c<=twokr[node][0]&&twokr[node][0]<=d)return ans+1; return -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...