| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 545422 | fadi57 | Rainforest Jumps (APIO21_jumps) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
//#include "jumps.h"
using namespace std;
const int mx=3e5+10;
typedef long long ll;
const ll mod=998244353 ;
const int SQ=400;
const ll inf=1e8+10;
int n;
int dp[20][mx],dp2[20][mx],lft[mx],right1[mx];vector<int>h;
void pre(){
for(int i=0;i<20;i++){
for(int j=0;j<n;j++){
if(i==0){
dp2[i][j]=right1[j];
}else{
if(dp2[i-1][j]==-1){
dp2[i][j]=-1;
}else{
dp2[i][j]=dp2[i-1][dp2[i-1][j]];
}
}
}
}
for(int i=0;i<20;i++){
for(int j=0;j<n;j++){
if(i==0){
if(h[lft[j]]>h[right1[j]]){
dp[i][j]=lft[j];
}else{
dp[i][j]=right1[j];
}
}else{
if(dp[i-1][j]!=-1){
dp[i][j]=dp[i-1][dp[i-1][j]];
}else{
dp[i][j]=-1;
}
}
}
}
}
void init(int N, vector<int>H) {
h=H;
n=N;
lft[0]=-1;
stack<int>s;
s.push(0);
for(int i=1;i<n;i++){
while(!s.empty()&&h[s.top()]<h[i]){
s.pop();
}
if(s.empty()){
lft[i]=-1;
}else{
lft[i]=s.top();
}
s.push(i);
}
right1[n-1]=-1;
while(!s.empty()){
s.pop();
}
s.push(n-1);
for(int i=n-2;i>=0;i--){
while(!s.empty()&&h[s.top()]<h[i]){
s.pop();
}
if(s.empty()){
right1[i]=-1;
}else{
right1[i]=s.top();
}
s.push(i);
}
pre();
}
int minimum_jumps(int A, int B, int C, int D) {
int a=A;int ans=0;int ans2=0;
for(int j=19;j>=0;j--){
if(dp2[j][a]!=-1&&h[dp2[j][a]]<=h[C]){
// cout<<j<<" "<<a<<endl;
a=dp2[j][a];
ans2+=(1<<j);
}
}
if(a!=C){return -1;}
a=A;
// cout<<a<<" "<<endl;
for(int j=19;j>=0;j--){
if(a==C){break;}
if(dp[j][a]!=-1&&h[dp[j][a]]<=h[C]){
// cout<<j<<" "<<a<<endl;
a=dp[j][a];
ans+=(1<<j);
}
}
if(a!=C){
for(int j=19;j>=0;j--){
if(a==C){break;}
if(dp2[j][a]!=-1&&h[dp2[j][a]]<=h[C]){
// cout<<j<<" "<<a<<endl;
a=dp2[j][a];
ans+=(1<<j);
}
}
}
return ans;
}
int main(){
/*
cin>>n;vector<int>v;
for(int i=0;i<n;i++){
int x;cin>>x;
v.push_back(x);
}
init(n,v);
pre();
int a,b,c,d; cin>>a>>b>>c>>d;
cout<<dp[0][a]<<" "<<dp[1][a]<<endl;
cout<<minimum_jumps(a,b,c,d);
*/
}