#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<long long, long long> ii;
long long inf = (1LL << 62LL);
///X, Y refers to points & buildings. L, R, H refers to skywalks
struct walk { long long l, r, h; };
struct vertex { long long x, y, id; };
long long min_distance(vector<int> X, vector<int> Y, vector<int> L, vector<int> R, vector<int> H, int START, int END) {
long long n = X.size(), m = L.size();
walk skywalks[m];
for(long long i = 0;i < m;i++) skywalks[i] = {L[i], R[i], H[i]};
vector<long long> useful[n];
useful[START].push_back(0);
useful[END].push_back(0);
for(walk w : skywalks){
useful[w.l].push_back(w.h);
useful[w.r].push_back(w.h);
}
///For skywalks crossing START and END, Split them
set<long long> aboveLine; ///A sweeping line going from bottom to top;
vector<long long> walkHeight; ///walk indeces sorted in increasing H
for(long long i = 0;i < m;i++) walkHeight.push_back(i);
sort(walkHeight.begin(), walkHeight.end(), [&](long long a, long long b) { return H[a] < H[b]; });
vector<ii> buildingHeight; ///building indeces soreted in increasing Y
for(long long i = 0;i < n;i++){
buildingHeight.push_back(ii(Y[i], i));
aboveLine.insert(i);
}
sort(buildingHeight.begin(), buildingHeight.end());
long long ptr = 0;
for(long long i = 0;i < m;i++){
long long w = walkHeight[i];
while(ptr < n && buildingHeight[ptr].first < H[w]){
aboveLine.erase(buildingHeight[ptr].second);
ptr++;
}
if(L[w] <= START && START <= R[w]){
auto it = aboveLine.lower_bound(START);
if(*it == START){
useful[START].push_back(H[w]);
}
else{
useful[*it].push_back(H[w]);
it--;
useful[*it].push_back(H[w]);
}
}
if(L[w] <= END && END <= R[w]){
auto it = aboveLine.lower_bound(END);
if(*it == END){
useful[END].push_back(H[w]);
}
else{
useful[*it].push_back(H[w]);
it--;
useful[*it].push_back(H[w]);
}
}
}
vector<ii> event[n]; ///process walks from left to right
for(walk w : skywalks){
event[w.l].push_back(ii(w.h, 1));
if(w.r != n-1) event[w.r+1].push_back(ii(w.h, -1));
}
multiset<long long> walkHeights;
for(long long i = 0;i < n;i++){
for(ii Ev : event[i]){
if(Ev.second == 1) walkHeights.insert(Ev.first);
else walkHeights.erase(walkHeights.find(Ev.first));
}
vector<long long> moreUseful; ///extra points to add to useful[i]
for(long long h : useful[i]){
multiset<long long>::iterator it = walkHeights.upper_bound(h);
//if(it != walkHeights.end()) moreUseful.push_back(*it);
if(it == walkHeights.begin()) continue;
it--;
if(it != walkHeights.begin()) moreUseful.push_back(*(--it));
}
for(long long u : moreUseful) useful[i].push_back(u);
sort(useful[i].begin(),useful[i].end());
useful[i].erase(unique(useful[i].begin(),useful[i].end()), useful[i].end());
while(useful[i].size() > 0 && useful[i].back() > Y[i]) useful[i].pop_back();
}
vector<vertex> vertices;
long long S, E; ///Start and End based on renumbering
long long idx = 0;
for(long long i = 0;i < n;i++){
if(i == START) S = idx;
if(i == END) E = idx;
for(long long y : useful[i]){
vertices.push_back({i, y, idx});
idx++;
}
}
//cout << S << " " << E << endl;
long long N = vertices.size(); ///big N is for no. of nodes on the graph
vector<ii> adj[N];
long long vis[N];
fill(vis, vis + N, inf);
/*
for(long long i = 0;i < N;i++){
vertex v = vertices[i];
cout << X[v.x] << " " << v.y << " " << v.id << '\n';
}
//*/
for(long long i = 1;i < N;i++){
if(vertices[i].x == vertices[i-1].x){
long long w = vertices[i].y - vertices[i-1].y;
adj[i].push_back(ii(w,i-1));
adj[i-1].push_back(ii(w,i));
}
}
unordered_map<long long, vector<ii> > hori; ///vertices on the same line
for(long long i = 0;i < N;i++){
hori[vertices[i].y].push_back(ii(vertices[i].x, vertices[i].id));
}
for(walk W : skywalks){
vector<ii> V = hori[W.h];
long long pos = lower_bound(V.begin(), V.end(), ii(W.l,-1)) - V.begin();
while(V[pos].first < W.r){
long long u = V[pos].second;
long long v = V[pos+1].second;
long long w = X[V[pos+1].first] - X[V[pos].first];
adj[u].push_back(ii(w,v));
adj[v].push_back(ii(w,u));
pos++;
}
}
///Dijkstra
priority_queue<ii, vector<ii>, greater<ii> > dij;
dij.push(ii(0,S)); vis[S] = 0;
while(!dij.empty()){
ii u = dij.top(); dij.pop();
for(ii v : adj[u.second]){
if(vis[v.second] > u.first + v.first){
vis[v.second] = u.first + v.first;
dij.push(ii(vis[v.second], v.second));
}
}
}
if(vis[E] >= inf) vis[E] = -1;
return vis[E];
}
