#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
int HASH = 1LL<<30;
int INF = 1LL<<61;
struct Node {
int building_num;
int height;
int ID;
};
int n,m;
long long min_distance(std::vector<signed> x, std::vector<signed> h, std::vector<signed> l, std::vector<signed> r, std::vector<signed> y, signed s, signed g) {
n = h.size();
m = y.size();
unordered_map<int,vector<pair<int,int>>> adjlist; //other node and weight
vector<vector<int>> skywalks_for_building(n);
vector<vector<int>> buildings_for_skywalk(m);
vector<Node> nodes; //building num, height
//approach to initialization: sort the skywalks by height, and maintain a set of 'alive' buildings
set<int> alive_buildings;
vector<int> sorted_building_indices(n); iota(sorted_building_indices.begin(), sorted_building_indices.end(), (int)0);
sort(sorted_building_indices.begin(), sorted_building_indices.end(), [&](const int i1, const int i2) {
return h[i1] < h[i2];
});
for (int i=0; i<n; i++) alive_buildings.insert(i);
vector<int> sorted_skywalk_indices(m); iota(sorted_skywalk_indices.begin(), sorted_skywalk_indices.end(), (int)0);
sort(sorted_skywalk_indices.begin(), sorted_skywalk_indices.end(), [&](const int i1, const int i2) {
return y[i1] < y[i2];
});
auto add_pair = [&](const int building_index, const int skywalk_index) {
//cout << "ADDING PAIR " << building_index << " " << skywalk_index << endl;
nodes.push_back({building_index, y[skywalk_index], building_index*HASH+y[skywalk_index]});
skywalks_for_building[building_index].push_back(skywalk_index);
buildings_for_skywalk[skywalk_index].push_back(building_index); //SHOULD NATURALLY BE SORTED BECAUSE WE GO IN INCREASING i
};
int building_pointer = 0;
for (int i:sorted_skywalk_indices) {
while (building_pointer<n && y[i] > h[sorted_building_indices[building_pointer]]) {
alive_buildings.erase(sorted_building_indices[building_pointer]);
building_pointer++;
}
int lval = l[i]; int rval = r[i];
auto lit = alive_buildings.lower_bound(lval);
if (lit==alive_buildings.end()) continue;
while (lit != alive_buildings.end() && *lit <= rval) {
add_pair(*lit, i);
lit = next(lit);
}
}*/
/*for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
if (l[j] <= i && i <= r[j] && y[j] <= h[i]) {
//cout << "WORKING " << i << " " << j << endl;
nodes.push_back({i, y[j], i*HASH+y[j]});
skywalks_for_building[i].push_back(j);
buildings_for_skywalk[j].push_back(i); //SHOULD NATURALLY BE SORTED BECAUSE WE GO IN INCREASING i
}
}
nodes.push_back({i,0,i*HASH});
}*/
for (int i=0; i<n; i++) {
nodes.push_back({i,0,i*HASH});
}
for (int i=0; i<n; i++) {
sort(skywalks_for_building[i].begin(), skywalks_for_building[i].end(), [&](const int i1, const int i2) {
return y[i1] < y[i2];
});
}
for (int j=0; j<m; j++) {
sort(buildings_for_skywalk[j].begin(), buildings_for_skywalk[j].end(), [&](const int i1, const int i2) {
return i1<i2;
});
}
auto add_edge = [&](int i1, int i2, int w) {
//cout << "ADDING EDGE " << i1/HASH << " " << i1%HASH << " " << i2/HASH << " " << i2%HASH << " " << w << endl;
adjlist[i1].push_back({i2,w});
adjlist[i2].push_back({i1,w});
};
for (int i=0; i<n; i++) {
for (int j=1; j<skywalks_for_building[i].size(); j++) {
int node_1 = i*HASH+y[skywalks_for_building[i][j]];
int node_2 = i*HASH+y[skywalks_for_building[i][j-1]];
int dist = y[skywalks_for_building[i][j]] - y[skywalks_for_building[i][j-1]];
add_edge(node_1, node_2, dist);
}
if (skywalks_for_building[i].size()>0) {
int node_1 = i*HASH+y[skywalks_for_building[i][0]];
int node_2 = i*HASH+0;
int dist = y[skywalks_for_building[i][0]];
add_edge(node_1, node_2, dist);
}
}
//cout << "HORIZONTAL " << endl;
for (int j=0; j<m; j++) {
//cout << j << " " << buildings_for_skywalk[j].size() << endl;
for (int i=1; i<buildings_for_skywalk[j].size(); i++) {
//cout << "TRYING " << i << " " << j << endl;
int node_1 = (buildings_for_skywalk[j][i])*HASH + y[j];
int node_2 = (buildings_for_skywalk[j][i-1])*HASH + y[j];
int dist = x[buildings_for_skywalk[j][i]] - x[buildings_for_skywalk[j][i-1]];
add_edge(node_1, node_2, dist);
}
}
int start_ID = s * HASH;
int end_ID = g * HASH;
priority_queue<pair<int,int>> distances; //naturally a maxheap so flip the signs
unordered_map<int,int> dist;
unordered_map<int,int> proc;
for (auto i:nodes) {
dist[i.ID] = INF;
}
dist[start_ID] = 0;
distances.push({-0, start_ID});
while (distances.size()) {
pair<int,int> top = distances.top();
distances.pop();
int di = -top.first;
int no = top.second;
//cout << "DOING " << di << " " << no << " " << adjlist[no].size() << endl;
if (dist[no] < di || proc[no]) continue;
proc[no] = 1;
for (auto edge:adjlist[no]) {
int nei = edge.first;
int wei = edge.second;
if (di+wei < dist[nei]) {
dist[nei] = di + wei;
distances.push({-dist[nei], nei});
}
}
}
int res = dist[end_ID];
if (res==INF) {
return -1;
}
return res;
}
