#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef long long ll;
void change(vi&l,vi &r,vi&y,vi&x,vi&h,int s)
{
int n=x.size(),q=l.size();
vector<pi> cur;
for(int i=0;i<n;i++)
{
cur.push_back({x[i],i});
}
for(int i=0;i<q;i++)
{
cur.push_back({y[i],-i-1});
}
set<int> have;
sort(begin(cur),end(cur));
reverse(begin(cur),end(cur));
vi lp,rp,yp;
for(int id=0;id<n+q;id++)
{
int i=cur[id].second;
if(i>=0)
{
// building
have.insert(i);
}
else
{
i=-i-1;
if(l[i]<s and s<r[i])
{
int a=-1,b=-1;
auto it=have.lower_bound(s);
if(it!=have.end())
b=*it;
it=have.upper_bound(s);
if(it!=begin(have))
{
it--;
a=*it;
}
if(b==-1)b=r[i];
if(a==-1)a=b;
lp.push_back(l[i]);
rp.push_back(a);
yp.push_back(y[i]);
lp.push_back(a);
rp.push_back(b);
yp.push_back(y[i]);
lp.push_back(b);
rp.push_back(r[i]);
yp.push_back(y[i]);
}
else
{
lp.push_back(l[i]);
rp.push_back(r[i]);
yp.push_back(y[i]);
}
// l[i] r[i]
}
}
// add maximum first
l=lp;
r=rp;
y=yp;
}
int n,q;
const int N=1e6+10;
set<pi> seg[N];
set<int> pts[N];
const ll inp=1e18;
ll dp[N];
void insert(int l,int r,int y,int i,int cl=0,int cr=n,int v=1)
{
if(r<cl or cr<l)return;
if(l<=cl and cr<=r)
{
seg[v].insert({y,i});
return;
}
int m=(cl+cr)>>1,lc=v<<1,rc=lc|1;
insert(l,r,y,i,cl,m,lc);
insert(l,r,y,i,m+1,cr,rc);
}
const int inf=2e9;
vector<pair<ll,int>> ma[N];
map<int,int> mp[N];
int lstp=0;
int get(int x,int y)
{
if(mp[x].find(y)==mp[x].end())
{
mp[x][y]=lstp++;
}
return mp[x][y];
}
pi upper_bound(int y,int i,int idx,int cl=0,int cr=n,int v=1)
{
if(i<cl or cr<i)
return {inf,inf};
auto it=seg[v].upper_bound({y,-inf});
pi ans={inf,inf};
// cout<<"at "<<cl<<' '<<cr<<' '<<v<<endl;
// cout<<y<<' '<<i<<' '<<idx<<endl;
if(it!=end(seg[v]) and it->second==idx)
{
// cout<<"matching "<<it->first<<' '<<it->second<<endl;
it++;
}
if(it!=end(seg[v]))ans=*it;
// cout<<"setting "<<ans.first<<' '<<ans.second<<endl;
if(cl==cr)return ans;
int m=(cl+cr)>>1,lc=v<<1,rc=lc|1;
pi ans1=upper_bound(y,i,idx,cl,m,lc);
if(ans1.first<ans.first)ans=ans1;
ans1=upper_bound(y,i,idx,m+1,cr,rc);
if(ans1.first<ans.first)ans=ans1;
return ans;
}
pi lower_bound(int y,int i,int idx,int cl=0,int cr=n,int v=1)
{
if(i<cl or cr<i)
return {-inf,-inf};
auto it=seg[v].lower_bound({y,-inf});
pi ans={-inf,-inf};
if(it!=begin(seg[v]))
{
it--;
ans=*it;
}
if(cl==cr)return ans;
int m=(cl+cr)>>1,lc=v<<1,rc=lc|1;
pi ans1=lower_bound(y,i,idx,cl,m,lc);
if(ans1.first>ans.first)ans=ans1;
ans1=lower_bound(y,i,idx,m+1,cr,rc);
if(ans1.first>ans.first)ans=ans1;
return ans;
}
long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
l.push_back(s);
l.push_back(g);
r.push_back(s);
r.push_back(g);
y.push_back(0);
y.push_back(0);
change(l,r,y,x,h,s);
change(l,r,y,x,h,g);
q=l.size();
n=x.size();
for(int i=0;i<q;i++)
{
insert(l[i],r[i],y[i],i);
}
for(int i=0;i<q;i++)
{
// cout<<"sovling for "<<i<<endl;
// cout<<l[i]<<' '<<r[i]<<' '<<y[i]<<endl;
pi it=upper_bound(y[i],r[i],i);
// cout<<"solved res "<<it.first<<' '<<it.second<<endl;
if(it.first!=inf and y[it.second]<=h[r[i]])
{
int j=it.second;
int cx=get(r[i],y[i]);
int nx=get(r[i],y[j]);
if(r[i]==5)
{
// cout<<"getting1 "<<y[i]<<' '<<y[j]<<endl;
}
ll d=abs(y[i]-y[j]);
pts[j].insert(r[i]);
ma[cx].push_back({d,nx});
ma[nx].push_back({d,cx});
}
it=upper_bound(y[i],l[i],i);
if(it.first!=inf and y[it.second]<=h[l[i]])
{
int j=it.second;
int cx=get(l[i],y[i]);
int nx=get(l[i],y[j]);
if(l[i]==5)
{
// cout<<"getting2 "<<y[i]<<' '<<y[j]<<endl;
}
ll d=abs(y[i]-y[j]);
pts[j].insert(l[i]);
ma[cx].push_back({d,nx});
ma[nx].push_back({d,cx});
}
it=lower_bound(y[i],r[i],i);
if(it.first!=-inf and y[it.second]<=h[r[i]])
{
int j=it.second;
int cx=get(r[i],y[i]);
int nx=get(r[i],y[j]);
if(r[i]==5)
{
// cout<<"getting3 "<<y[i]<<' '<<y[j]<<endl;
}
ll d=abs(y[i]-y[j]);
pts[j].insert(r[i]);
ma[cx].push_back({d,nx});
ma[nx].push_back({d,cx});
}
it=lower_bound(y[i],l[i],i);
if(it.first!=-inf and y[it.second]<=h[l[i]])
{
int j=it.second;
int cx=get(l[i],y[i]);
int nx=get(l[i],y[j]);
if(l[i]==5)
{
// cout<<"getting4 "<<y[i]<<' '<<y[j]<<endl;
}
ll d=abs(y[i]-y[j]);
pts[j].insert(l[i]);
ma[cx].push_back({d,nx});
ma[nx].push_back({d,cx});
}
int cx=get(l[i],y[i]);
int nx=get(r[i],y[i]);
ll d=abs(x[r[i]]-x[l[i]]);
ma[cx].push_back({d,nx});
ma[nx].push_back({d,cx});
pts[i].insert(l[i]);
pts[i].insert(r[i]);
}
for(int i=0;i<n;i++)
{
for(auto [y,id]:mp[i])
{
// cout<<"hola "<<i<<' '<<y<<' '<<id<<endl;
}
}
for(int i=0;i<q;i++)
{
vector<int> cul(begin(pts[i]),end(pts[i]));
for(int j=1;j<cul.size();j++)
{
int cx=get(cul[j],y[i]);
int nx=get(cul[j-1],y[i]);
ll d=abs(x[cul[j]]-x[cul[j-1]]);
ma[cx].push_back({d,nx});
ma[nx].push_back({d,cx});
}
}
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>>pq;
for(int i=0;i<N;i++)dp[i]=inp;
dp[get(s,0)]=0;
pq.push({0,get(s,0)});
while(pq.size())
{
auto [mn,x]=pq.top();
pq.pop();
if(dp[x]!=mn)continue;
// cout<<"PQ "<<x<<' '<<dp[x]<<endl;
for(auto [w,y]:ma[x])
{
// cout<<w<<' '<<y<<' '<<x<<endl;
if(dp[y]>dp[x]+w)
{
// cout<<"updating "<<y<<" from "<<x<<' '<<w<<endl;
dp[y]=dp[x]+w;
pq.push({dp[y],y});
}
}
}
return dp[get(g,0)];
}
