#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool minimize(T& a, T b){
if(a > b){
a = b;
return true;
}
return false;
}
vector<int>x, h, l, r, y;
int n, m, s, t;
namespace sub1{
struct Data{
int x, y;
ll w;
Data(){}
Data(int _x, int _y, ll _w) : x(_x), y(_y), w(_w) {}
friend bool operator <(const Data a, const Data b){
return a.w > b.w;
}
};
ll solve(){
map<pair<int, int>, ll>d;
priority_queue<Data>pq;
pq.push(Data(x[s], 0, d[make_pair(x[s], 0)] = 0));
while(!pq.empty()){
auto [px, py, dw] = pq.top();
pq.pop();
if(dw == d[make_pair(px, py)]){
int idx = lower_bound(x.begin(), x.end(), px) - x.begin();
for(int i = 0; i < m; i++){
if(l[i] <= idx && r[i] >= idx && h[idx] >= y[i]){
ll dnw = dw + abs(py - y[i]);
map<pair<int, int>, ll>::iterator it = d.find(make_pair(px, y[i]));
if(it == d.end() || it->second > dnw){
pq.push(Data(px, y[i], d[make_pair(px, y[i])] = dnw));
}
if(py == y[i]){
for(int j = l[i]; j <= r[i]; j++){
if(h[j] >= y[i]){
dnw = dw + abs(px - x[j]);
if((it = d.find(make_pair(x[j], py))) == d.end() || it->second > dnw){
pq.push(Data(x[j], py, d[make_pair(x[j], py)] = dnw));
}
}
}
}
}
}
auto it = d.find(make_pair(px, 0));
dw += py;
if(it == d.end() || it->second > dw){
pq.push(Data(px, 0, d[make_pair(px, 0)] = dw));
}
}
}
auto it = d.find(make_pair(x[t], 0));
return it == d.end() ? -1 : it->second;
}
}
const ll INF = 1e18;
const int lim = 1e5 + 5;
namespace sub34{
const int LIM = 1e9 + 36;
struct DynamicSegmentTree{
struct Node{
ll val;
int lc, rc;
Node(){
lc = rc = -1;
val = INF;
}
};
vector<Node>st;
DynamicSegmentTree(){
st.push_back(Node());
}
void new_node(int id){
if(st[id].lc == -1){
st[id].lc = st.size();
st.push_back(Node());
}
if(st[id].rc == -1){
st[id].rc = st.size();
st.push_back(Node());
}
}
void update(int id, int l, int r, int p, ll x){
if(l == r){
st[id].val = x;
return;
}
int m = (l + r) >> 1;
new_node(id);
if(m < p){
update(st[id].rc, m + 1, r, p, x);
}
else{
update(st[id].lc, l, m, p, x);
}
st[id].val = min(st[st[id].lc].val, st[st[id].rc].val);
}
ll get(int id, int l, int r, int u, int v){
if(l > v || r < u || id == -1){
return INF;
}
if(u <= l && v >= r){
return st[id].val;
}
int m = (l + r) >> 1;
return min(get(st[id].lc, l, m, u, v), get(st[id].rc, m + 1, r, u, v));
}
};
DynamicSegmentTree st_plus, st_minus;
ll solve(){
vector<vector<int>>event(n + 1);
map<int, vector<pair<int, int>>>range;
for(int i = 0; i < m; i++){
range[y[i]].push_back(make_pair(l[i], r[i]));
}
for(auto& [vy, ve] : range){
sort(ve.begin(), ve.end());
int L = ve[0].first, R = ve[0].second;
for(int i = 1; i < ve.size(); i++){
if(ve[i].first == R){
R = ve[i].second;
}
else{
event[L].push_back(vy);
event[R + 1].push_back(-vy);
tie(L, R) = ve[i];
}
}
event[L].push_back(vy);
event[R + 1].push_back(-vy);
}
for(int& vy : event[0]){
st_plus.update(0, 0, LIM, vy, vy << 1);
st_minus.update(0, 0, LIM, vy, 0);
}
for(int i = 1; i < n; i++){
sort(event[i].begin(), event[i].end());
for(int& vy : event[i]){
if(vy < 0){
st_plus.update(0, 0, LIM, -vy, INF);
st_minus.update(0, 0, LIM, -vy, INF);
}
else{
ll x = min(st_plus.get(0, 0, LIM, vy, LIM) - vy, st_minus.get(0, 0, LIM, 0, vy) + vy);
st_plus.update(0, 0, LIM, vy, x + vy);
st_minus.update(0, 0, LIM, vy, x - vy);
}
}
}
return st_plus.st[0].val == INF ? -1 : st_plus.st[0].val + x[n - 1] - x[0];
}
}
namespace sub25{
const int LIM = 18e5 + 36;
vector<pair<int, int>>g[LIM];
pair<int, int>lst[lim];
int ptr_ph, N = 0;
ll dis[LIM];
void add_sky_walk(int L, int R, int Y){
l.push_back(L);
r.push_back(R);
y.push_back(Y);
}
void add_edge(int u, int v, int w){
g[u].push_back(make_pair(v, w));
g[v].push_back(make_pair(u, w));
}
ll solve(){
vector<pair<int, int>>ph(n);
for(int i = 0; i < n; i++){
ph[i] = make_pair(h[i], i);
}
sort(ph.begin(), ph.end(), greater<pair<int, int>>());
for(int x : {s, t}){
vector<pair<int, int>>py(m);
for(int i = ptr_ph = 0; i < m; i++){
py[i] = make_pair(y[i], i);
}
sort(py.begin(), py.end(), greater<pair<int, int>>());
set<int>S;
for(auto& [vy, i] : py){
while(ptr_ph < n && ph[ptr_ph].first >= vy){
S.insert(ph[ptr_ph++].second);
}
if(l[i] < x && r[i] > x){
int left = *prev(S.upper_bound(x)), right = *S.lower_bound(x);
if(r[i] > right){
add_sky_walk(right, r[i], vy);
}
if(l[i] < left){
add_sky_walk(l[i], left, vy);
}
if(left < right){
add_sky_walk(left, right, vy);
}
}
}
m = l.size();
}
vector<pair<int, int>>py(m);
for(int i = ptr_ph = 0; i < m; i++){
py[i] = make_pair(y[i], i);
}
sort(py.begin(), py.end(), greater<pair<int, int>>());
set<int>S;
fill(lst, lst + n, make_pair(-1, -1));
for(auto& [vy, i] : py){
while(ptr_ph < n && ph[ptr_ph].first >= vy){
S.insert(ph[ptr_ph++].second);
}
S.insert(l[i]);
S.insert(r[i]);
vector<int>trash;
int pre_cix = -1;
for(auto it = S.find(l[i]); it != S.end() && *it <= r[i]; it++){
int cix = *it;
if(lst[cix].first != -1){
add_edge(N, lst[cix].first, lst[cix].second - vy);
}
if(pre_cix != -1){
add_edge(N, N - 1, x[cix] - x[pre_cix]);
}
lst[pre_cix = cix] = make_pair(N++, vy);
if(cix != l[i] && cix != r[i]){
trash.push_back(cix);
}
}
for(int& x : trash){
S.erase(x);
}
}
for(int x : {s, t}){
if(lst[x].first == -1){
return -1;
}
add_edge(lst[x].first, N++, lst[x].second);
}
memset(dis, 0x0f, sizeof(dis));
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>>pq;
pq.push(make_pair(dis[N - 2] = 0, N - 2));
while(!pq.empty()){
auto [cw, cu] = pq.top();
pq.pop();
if(cw == dis[cu]){
for(auto& [ev, ew] : g[cu]){
if(minimize(dis[ev], cw + ew)){
pq.push(make_pair(dis[ev], ev));
}
}
}
}
return dis[N - 1] > INF ? -1 : dis[N - 1];
}
}
ll min_distance(vector<int>_x, vector<int>_h, vector<int>_l, vector<int>_r, vector<int>_y, int _s, int _t){
s = _s;
t = _t;
swap(x, _x);
swap(h, _h);
swap(l, _l);
swap(r, _r);
swap(y, _y);
if(max(n = x.size(), m = l.size()) <= 50){
return sub1::solve();
}
if(s == 0 && t == n - 1){
return sub34::solve();
}
return sub25::solve();
}
