#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;
class SegmentTree
{
public:
int getLeft(int node) { return 2*node; }
int getRight(int node) { return 2*node + 1; }
void update(int node, int l, int r, int i, lli v)
{
if( i < l || r < i ) return;
if( l == r )
{
mn[node] = v;
return;
}
int m = ( l + r )/2;
update( getLeft(node) , l , m , i , v );
update( getRight(node) , m + 1 , r , i , v );
mn[node] = min( mn[ getLeft(node) ] , mn[ getRight(node) ] );
}
lli query(int node, int l, int r, int i, int j)
{
if( j < l || r < i ) return INF;
if( i <= l && r <= j ) return mn[node];
int m = ( l + r )/2;
lli mnLeft = query( getLeft(node) , l , m , i , j );
lli mnRight = query( getRight(node) , m + 1 , r , i , j );
return min( mnLeft , mnRight );
}
SegmentTree()
{
for(int i = 0 ; i < 4*MAXN ; i++)
mn[i] = INF;
}
private:
lli mn[4*MAXN];
};
int n, m;
int cntNode;
bool wasUpdated[MAXN];
vector< int > sweep[MAXN];
vector< int > building[MAXN];
vector< int > intersection[MAXN];
map< int , int > realY;
SegmentTree up;
SegmentTree down;
void compress(vector<int>& v)
{
set< int > s;
map< int , int > conv;
for(int i = 0 ; i < (int) v.size() ; i++)
s.insert( v[i] );
int cnt = 0;
for(auto it = s.begin() ; it != s.end() ; it++)
{
conv[ *it ] = ++cnt;
realY[ cnt ] = *it;
}
for(int i = 0 ; i < (int) v.size() ; i++)
v[i] = conv[ v[i] ];
}
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();
compress( y );
for(int i = 0 ; i < m ; i++)
{
sweep[ l[i] ].push_back( -i - 1 );
sweep[ r[i] ].push_back( i + 1 );
building[ l[i] ].push_back( y[i] );
building[ r[i] ].push_back( y[i] );
}
for(int i = 0 ; i < (int) building[b].size() ; i++)
{
int curHeight = building[b][i];
up.update( 1 , 1 , m , curHeight , 2*realY[ curHeight ] );
down.update( 1 , 1 , m , curHeight , 0 );
}
lli ans = INF;
for(int i = n - 2 ; i >= 0 ; i--)
{
sort( sweep[i].begin() , sweep[i].end() );
vector< int > all;
vector< pair<lli,int> > updates;
while( !sweep[i].empty() && sweep[i].back() > 0 )
{
int cur = sweep[i].back(); cur = cur - 1;
sweep[i].pop_back();
all.push_back( y[cur] );
wasUpdated[ y[cur] ] = true;
lli ansUp = up.query( 1 , 1 , m , y[cur] , m );
lli ansDown = down.query( 1 , 1 , m , 1 , y[cur] );
ansUp -= realY[ y[cur] ];
ansDown += realY[ y[cur] ];
lli curAns = min( ansUp , ansDown );
updates.push_back( { curAns , y[cur] } );
}
while( !updates.empty() )
{
lli curVal = updates.back().first;
int curHeight = updates.back().second;
updates.pop_back();
up.update( 1 , 1 , m , curHeight , curVal + realY[ curHeight ] );
down.update( 1 , 1 , m , curHeight , curVal - realY[ curHeight ] );
}
if( i == 0 )
ans = up.query( 1 , 1 , m , 1 , m );
while( !sweep[i].empty() )
{
int cur = sweep[i].back(); cur = -cur - 1;
sweep[i].pop_back();
if( wasUpdated[ y[cur] ] ) continue;
up.update( 1 , 1 , m , y[cur] , INF );
down.update( 1 , 1 , m , y[cur] , INF );
}
while( !all.empty() )
{
wasUpdated[ all.back() ] = false;
all.pop_back();
}
}
ans += x[n - 1] - x[0];
if( ans >= INF ) return -1;
return ans;
}
