#include "jumps.h" #include <bits/stdc++.h> using namespace std; const int N=200050; const int LOG=25; int a[N],l[N],r[N],mn[N][LOG],mx[N][LOG],L[N][LOG],st[N][LOG]; int getmx(int l,int r){ int res=0; for(int i=LOG-1;~i;i--)if(l+(1<<i)-1<=r)res=max(res,st[l][i]),l+=(1<<i); return res; } void init(int n,vector<int> h){ for(int i=1;i<=n;i++)a[i]=h[i-1],st[i][0]=a[i]; for(int j=1;j<LOG;j++)for(int i=1;i+(1<<j)<=n+1;i++)st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]); stack<int> stk; for(int i=1;i<=n;i++){ while(!stk.empty()&&a[stk.top()]<a[i])stk.pop(); if(!stk.empty())l[i]=stk.top(); else l[i]=0; stk.push(i); } while(stk.size())stk.pop(); for(int i=n;i>=1;i--){ while(!stk.empty()&&a[stk.top()]<a[i])stk.pop(); if(!stk.empty())r[i]=stk.top(); else r[i]=0; stk.push(i); } for(int i=1;i<=n;i++){ if(r[i]!=0&&(l[i]==0||a[l[i]]>a[r[i]]))mn[i][0]=r[i]; else mn[i][0]=l[i]; if(r[i]!=0&&(l[i]==0||a[l[i]]<a[r[i]]))mx[i][0]=r[i]; else mx[i][0]=l[i]; L[i][0]=l[i]; } for(int j=1;j<LOG;j++){ for(int i=1;i<=n;i++){ mn[i][j]=mn[mn[i][j-1]][j-1]; mx[i][j]=mx[mx[i][j-1]][j-1]; L[i][j]=L[L[i][j-1]][j-1]; } } } bool check(int A,int B){ for(int i=LOG-1;~i;i--)if(mn[A][i]!=0&&a[mn[A][i]]<=a[B])A=mn[A][i]; return A==B; } int minimum_jumps(int A,int B,int C,int D){ A++;B++;C++;D++; // if(!check(A,C))return -1; int x=getmx(C,D),pos=B; for(int i=LOG-1;~i;i--)if(L[pos][i]>=A&&r[L[pos][i]]<=D)pos=L[pos][i]; // if(a[pos]>x)return -1; int ans=0; for(int i=LOG-1;~i;i--){ if(mx[pos][i]>0&&mx[pos][i]<C&&r[mx[pos][i]]!=0&&r[mx[pos][i]]<=D)pos=mx[pos][i],ans+=(1<<i); } for(int i=LOG-1;~i;i--){ if(mn[pos][i]>0&&r[mn[pos][i]]!=0&&r[mn[pos][i]]<=D&&mn[pos][i]<C)pos=mn[pos][i],ans+=(1<<i); assert(pos<=D); } if(r[pos]>=C&&r[pos]<=D)ans++,pos=r[pos]; if(pos>=C&&pos<=D)return ans; return -1; } //int main(){ // int d; // scanf("%d",&d); // vector<int> A(d); // for(int i=0;i<d;i++)scanf("%d",&A[i]); // init(d,A); // printf("%d\n",minimum_jumps(4,4,6,6)); // printf("%d\n",minimum_jumps(1,3,5,6)); // printf("%d\n",minimum_jumps(0,1,2,2)); // return 0; //} /* 7 3 2 1 6 4 5 7 */

jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:51:6: warning: unused variable 'x' [-Wunused-variable]
   51 |  int x=getmx(C,D),pos=B;
      |      ^