#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef pair<int,int> pii;
const int MAXN = 2000010;
const lli INF = 1000000000000000000LL;
int n, m;
int cntNode;
lli dist[MAXN];
vector< int > adj[MAXN];
vector< int > weight[MAXN];
vector< int > sweep[MAXN];
vector< int > building[MAXN];
vector< int > intersection[MAXN];
map< int , int > indNode[MAXN];
void buildEdge(int U, int V, int W)
{
adj[U].push_back( V );
adj[V].push_back( U );
weight[U].push_back( W );
weight[V].push_back( W );
}
void Dijkstra(int S)
{
set< pair<lli,int> > s;
for(int i = 1 ; i <= cntNode ; i++)
dist[i] = INF;
dist[S] = 0;
s.insert( { 0 , S } );
while( !s.empty() )
{
int cur = s.begin()->second;
s.erase( s.begin() );
for(int i = 0 ; i < (int) adj[cur].size() ; i++)
{
int viz = adj[cur][i];
int w = weight[cur][i];
if( dist[viz] > dist[cur] + w )
{
s.erase( { dist[viz] , viz } );
dist[viz] = dist[cur] + w;
s.insert( { dist[viz] , viz } );
}
}
}
}
long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int a, int b)
{
n = x.size(); m = l.size();
for(int i = 0 ; i < m ; i++)
{
sweep[ l[i] ].push_back( i + 1 );
sweep[ r[i] + 1 ].push_back( -i - 1 );
}
set< pii > s;
for(int i = 0 ; i < n ; i++)
{
indNode[i][0] = ++cntNode;
building[i].push_back( 0 );
while( !sweep[i].empty() )
{
int cur = sweep[i].back();
sweep[i].pop_back();
if( cur > 0 ) s.insert( { y[cur - 1] , cur - 1 } );
else s.erase( { y[-cur - 1] , -cur - 1 } );
}
for(auto it = s.begin() ; it != s.end() ; it++)
{
int curY = it->first;
int curSkyWalking = it->second;
if( curY > h[i] ) break;
indNode[i][curY] = ++cntNode;
buildEdge( cntNode - 1 , cntNode , curY - building[i].back() );
building[i].push_back( curY );
intersection[ curSkyWalking ].push_back( i );
}
}
for(int i = 0 ; i < m ; i++)
{
for(int j = 0 ; j < (int) intersection[i].size() - 1 ; j++)
{
int U = intersection[i][j];
int V = intersection[i][j + 1];
int W = x[V] - x[U];
U = indNode[U][ y[i] ];
V = indNode[V][ y[i] ];
buildEdge( U , V , W );
}
}
int S = indNode[a][0];
int T = indNode[b][0];
Dijkstra( S );
if( dist[T] == INF ) return -1;
return dist[T];
}
