#include "walk.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("fast-math")
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const ll INF=1e18;
int n,m;
int ind;
vector<pii> muchii[1000005];
vector<pii> nodes[1000005];
vector<int> where[100005];
int arb[4*100005],toprop[4*100005];
ll dp[100005];
struct skywalk
{
ll l,r,h,ind;
} v[100005];
ll dist[1000005];
bool comp(pii a,pii b)
{
return a.second<b.second;
}
bool cresc(skywalk a, skywalk b)
{
if(a.h!=b.h)
return a.h<b.h;
return a.l>b.l;
}
bool byr(skywalk a, skywalk b)
{
return a.r<b.r;
}
bool descresc(skywalk a, skywalk b)
{
if(a.h!=b.h)
return a.h>b.h;
return a.l>b.l;
}
void addnode(int x,int y)
{
ind++;
nodes[x].push_back({y,ind});
}
bool use[2000005];
void bfs()
{
for(int i=1;i<=ind;i++)
dist[i]=INF;
dist[1]=0;
priority_queue<pll,vector<pll>, greater<pll>> pq;
pq.push({0,1});
while(!pq.empty())
{
int nod=pq.top().second;
if(nod==2)
return;
pq.pop();
if(use[nod])
continue;
use[nod]=1;
for(auto i:muchii[nod])
if(dist[i.first]>dist[nod]+i.second)
{
dist[i.first]=dist[nod]+i.second;
pq.push({dist[i.first],i.first});
}
}
}
void prop(int nod)
{
int val=toprop[nod];
arb[nod*2]=val;
arb[nod*2+1]=val;
toprop[nod*2]=val;
toprop[nod*2+1]=val;
}
void build(int nod,int st,int dr)
{
arb[nod]=-1;
toprop[nod]=-1;
if(st==dr)
return;
int mij=(st+dr)/2;
build(nod*2,st,mij);
build(nod*2+1,mij+1,dr);
}
void update(int nod,int st,int dr,int a,int b,int val)
{
if(toprop[nod]!=-1&&st!=dr)
prop(nod);
toprop[nod]=-1;
if(st>=a&&dr<=b)
{
arb[nod]=val;
toprop[nod]=val;
return;
}
int mij=(st+dr)/2;
if(a<=mij)
update(nod*2,st,mij,a,b,val);
if(b>mij)
update(nod*2+1,mij+1,dr,a,b,val);
}
int query(int nod,int st,int dr,int poz)
{
if(toprop[nod]!=-1&&st!=dr)
prop(nod);
toprop[nod]=-1;
if(st==dr)
return arb[nod];
int mij=(st+dr)/2;
if(poz<=mij)
return query(nod*2,st,mij,poz);
else
return query(nod*2+1,mij+1,dr,poz);
}
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)
{
n=x.size();
m=l.size();
if(x.size()<=50&&l.size()<=50)
{
addnode(s,0);
addnode(g,0);
for(int i=0;i<l.size();i++)
{
int prv=-1;
for(int j=l[i];j<=r[i];j++)
if(y[i]<=h[j])
{
addnode(j,y[i]);
if(prv!=-1)
{
int a=ind-1;
int b=ind;
muchii[a].push_back({b,x[j]-x[prv]});
muchii[b].push_back({a,x[j]-x[prv]});
}
prv=j;
}
}
for(int i=0;i<n;i++)
if(!nodes[i].empty())
{
sort(nodes[i].begin(),nodes[i].end());
for(int j=1;j<nodes[i].size();j++)
{
ll d=nodes[i][j].first-nodes[i][j-1].first;
ll a=nodes[i][j].second;
ll b=nodes[i][j-1].second;
muchii[a].push_back({b,d});
muchii[b].push_back({a,d});
}
}
bfs();
if(dist[2]==INF)
return -1;
return dist[2];
}
for(int i=0;i<m;i++)
v[i]={l[i],r[i],y[i],i};
sort(v,v+m,cresc);
build(1,0,n-1);
for(int i=0;i<m;i++)
{
int rgt=v[i].r;
int val=query(1,0,n-1,rgt);
if(val!=-1)
where[v[i].ind].push_back(val);
update(1,0,n-1,v[i].l,v[i].r,v[i].ind);
}
sort(v,v+m,descresc);
build(1,0,n-1);
for(int i=0;i<m;i++)
{
int rgt=v[i].r;
int val=query(1,0,n-1,rgt);
if(val!=-1)
where[v[i].ind].push_back(val);
update(1,0,n-1,v[i].l,v[i].r,v[i].ind);
}
ll ans=INF;
sort(v,v+m,byr);
for(int i=0;i<m;i++)
dp[i]=INF;
for(int i=0;i<m;i++)
{
ll ind=v[i].ind;
if(v[i].l==0)
dp[ind]=min(dp[ind],v[i].h);
if(v[i].r==n-1)
ans=min(ans,dp[ind]+v[i].h+x[n-1]-x[0]);
for(int j:where[ind])
dp[j]=min(dp[j],dp[ind]+abs(y[j]-y[ind]));
}
if(ans==INF)
return -1;
return ans;
}
