#include "walk.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
using oset = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
long long min_distance(std::vector<int> x, std::vector<int> h,
std::vector<int> l, std::vector<int> r, std::vector<int> y, int st, int ed) {
#define int long long
int n = h.size();
int m = y.size();
vector<int> bl;
vector<int> br(m);
bl.resize(n);
iota(bl.begin(),bl.end(), 0);
iota(br.begin(),br.end(), 0);
sort(bl.begin(), bl.end(), [&](int u, int v) -> bool {
return h[u] > h[v];
});
sort(br.begin(), br.end(), [&](int u, int v) -> bool {
return y[u] > y[v];
});
int p1 = 0;
set<int> s;
map<int,vector<int>> mp;
map<int,vector<int>> coords;
vector<vector<pair<int,long long>>> g;
map<pair<int,int>, int> cmp;
auto add = [&](int x, int y) -> int {
if(cmp.find(pair<int,int>(x, y))!=cmp.end())return cmp[{x, y}];
cmp[{x,y}]=g.size();
coords[x].push_back(y);
g.push_back({});
return cmp[{x,y}];
};
for(int i = 0;i<m;i++) {
while(p1 < n and h[bl[p1]] >= y[br[i]]) {
mp[x[bl[p1]]].push_back(bl[p1]);
s.insert(x[bl[p1++]]);
}
int prev=-1;
for(auto it = s.lower_bound(x[l[br[i]]]);it!=s.end();it++) {
if((*it) > x[r[br[i]]])break;
int at = (*it);
// cout << y[br[i]] << " " << at << endl;
if(coords[at].size())
coords[at].push_back(y[br[i]]);
else coords[at].push_back(0);
add(at, y[br[i]]);
add(at, 0);
if(prev!=-1) {
g[add(prev, y[br[i]])].push_back({add(at, y[br[i]]), abs(at-prev)});
g[add(at, y[br[i]])].push_back({add(prev, y[br[i]]), abs(at-prev)});
}
prev=at;
}
}
for(auto &i:coords) {
sort(i.second.begin(), i.second.end());
for(int j = 1;j<(int)(i.second).size();j++) {
// cout << i.first << " " << i.second[j-1] << " " << i.second[j] << endl;
// cout << i.first << " " << i.second[j-1] << " " << i.second[j] << endl;
g[add(i.first, i.second[j-1])].push_back({add(i.first, i.second[j]), abs(i.second[j]-i.second[j-1])});
g[add(i.first, i.second[j])].push_back({add(i.first, i.second[j-1]), abs(i.second[j]-i.second[j-1])});
}
}
// cout << endl;
priority_queue<pair<long long,int>> pq;
pq.push(pair<long long, int>(0ll, add(x[st], 0)));
vector<long long> dist(g.size(), (long long)2e18);
dist[add(x[st], 0)] = 0;
map<int, pair<int,int>> revs;
for(auto i:cmp) {
revs[i.second] = i.first;
}
vt<bool> vis(g.size());
while(pq.size()) {
int at = pq.top().second;
if(vis[at])return;
vis[at]=1;
// cout << revs[at].first << " " << revs[at].second << " " << dist[at] << endl;
pq.pop();
for(auto [to, w]:g[at]){
if(dist[to] > dist[at] + w) {
dist[to] = dist[at]+w;
pq.push(pair<long long, int> (-dist[to], to));
}
}
}
return dist[add(x[ed], 0)];
#undef int
}
Compilation message
walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:83:2: error: 'vt' was not declared in this scope; did you mean 'st'?
83 | vt<bool> vis(g.size());
| ^~
| st
walk.cpp:83:5: error: expected primary-expression before 'bool'
83 | vt<bool> vis(g.size());
| ^~~~
walk.cpp:86:6: error: 'vis' was not declared in this scope
86 | if(vis[at])return;
| ^~~
walk.cpp:86:14: error: return-statement with no value, in function returning 'long long int' [-fpermissive]
86 | if(vis[at])return;
| ^~~~~~
walk.cpp:87:3: error: 'vis' was not declared in this scope
87 | vis[at]=1;
| ^~~
