#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define Time (clock() * 1.0 / CLOCKS_PER_SEC)
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1& x, T2 y) {
return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1& x, T2 y) {
return y > x ? (x = y, true) : false;
}
void debug_out() {
cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
cerr << ' ' << A;
debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
for (int i = 0; i < n; ++i) {
cerr << a[i] << ' ';
}
cerr << endl;
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
#define debug(...) 1337
#define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) {
for (auto& e : v) {
stream << e << ' ';
}
return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
return stream << p.first << ' ' << p.second;
}
#define int ll
const ll INF64 = 1e18;
#ifdef LOCAL
const int maxN = 50;
const int maxV = 150;
#else
const int maxN = 1e5 + 5;
const int maxV = 4e6 + 6;
#endif
int n, m;
int V;
vector<pii> G[maxV];
ll dist[maxV];
priority_queue<pli> pq;
set<int> points[maxN];
map<int, int> ptIdx[maxN];
int getIdx(int i, int y) {
if (ptIdx[i].count(y))
return ptIdx[i][y];
return ptIdx[i][y] = V++;
}
void addEdge(int u, int v, int w) {
G[u].emplace_back(v, w);
G[v].emplace_back(u, w);
}
namespace sgt {
const int logN = 17;
const int N = 1 << logN;
int mx[2 * N];
void build(vector<int>& H) {
for (int i = 0; i < n; ++i)
mx[i + N] = H[i];
for (int i = N - 1; i >= 1; --i)
mx[i] = max(mx[i << 1], mx[i << 1 | 1]);
}
int getFirstGeq(int v, int vl, int vr, int l, int r, int x) {
if (l > r || vr < l || r < vl || mx[v] < x) return -1;
if (vl == vr) return vl;
int vm = (vl + vr) >> 1;
int al = getFirstGeq(v << 1, vl, vm, l, r, x);
if (al != -1)
return al;
return getFirstGeq(v << 1 | 1, vm + 1, vr, l, r, x);
}
int getFirstGeq(int l, int r, int x) {
return getFirstGeq(1, 0, N - 1, l, r, x);
}
int getLastGeq(int v, int vl, int vr, int l, int r, int x) {
if (l > r || vr < l || r < vl || mx[v] < x) return -1;
if (vl == vr) return vl;
int vm = (vl + vr) >> 1;
int ar = getLastGeq(v << 1 | 1, vm + 1, vr, l, r, x);
if (ar != -1)
return ar;
return getLastGeq(v << 1, vl, vm, l, r, x);
}
int getLastGeq(int l, int r, int x) {
return getLastGeq(1, 0, N - 1, l, r, x);
}
}
ll min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int si, int ti) {
n = X.size(), m = L.size();
int S, T;
for (int i = 0; i < n; ++i) {
int v = getIdx(i, 0);
if (i == si)
S = v;
if (i == ti)
T = v;
}
sgt::build(H);
struct Event {
int i, tp, j;
Event() {}
Event(int _i, int _tp, int _j): i(_i), tp(_tp), j(_j) {}
bool operator < (const Event& e) const {
if (i != e.i)
return i < e.i;
return tp < e.tp;
}
};
vector<Event> ev;
for (int j = 0; j < m; ++j) {
int l = L[j], r = R[j], y = Y[j];
auto& p = points[j];
p.insert(l);
p.insert(r);
for (int i : {si, ti}) {
if (i <= r)
p.insert(sgt::getFirstGeq(max(l, i), r, y));
if (i >= l)
p.insert(sgt::getLastGeq(l, min(r, i), y));
}
ev.emplace_back(l + 1, 0, j);
ev.emplace_back(r, 1, j);
for (int i : p)
ev.emplace_back(i, 2, j);
}
sort(all(ev));
set<pii> open;
for (auto& e : ev) {
if (e.tp == 0) {
open.insert({Y[e.j], e.j});
} else if (e.tp == 1) {
open.erase({Y[e.j], e.j});
} else {
int y = Y[e.j];
// debug(e.i, y, e.j);
// for (auto el : open) cerr << el << "; "; cerr << endl;
auto it = open.lower_bound({y, -1});
if (it != open.begin()) {
it = prev(it);
int y1 = it->fi;
int j1 = it->se;
getIdx(e.i, y1);
points[j1].insert(e.i);
}
}
}
for (int j = 0; j < m; ++j) {
// debug(j);
// for (auto i : points[j])
// cerr << i << ' ';
// cerr << endl;
int y = Y[j];
int last_i = -1;
int last_v = -1;
for (int i : points[j]) {
int v = getIdx(i, y);
if (last_i != -1) {
addEdge(last_v, v, X[i] - X[last_i]);
}
last_i = i;
last_v = v;
}
}
for (int i = 0; i < n; ++i) {
int last_v = -1;
int last_y = -1;
// debug(i);
for (auto& [y, v] : ptIdx[i]) {
// cerr << y << ' ';
if (last_v != -1) {
addEdge(last_v, v, y - last_y);
}
last_v = v;
last_y = y;
}
// cerr << endl;
}
fill(dist, dist + V, INF64);
dist[S] = 0;
pq.push({0, S});
while (!pq.empty()) {
int v = pq.top().se;
ll d = -pq.top().fi;
pq.pop();
if (d != dist[v]) continue;
if (v == T) return dist[v];
for (auto& [u, w] : G[v])
if (chkmin(dist[u], dist[v] + w))
pq.push({-dist[u], u});
}
return -1;
}
#ifdef LOCAL
int32_t main() {
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
assert(2 == scanf("%d%d", &n, &m));
vector<int> x(n), h(n);
for (int i = 0; i < n; i++)
assert(2 == scanf("%d%d", &x[i], &h[i]));
vector<int> l(m), r(m), y(m);
for (int i = 0; i < m; i++)
assert(3 == scanf("%d%d%d", &l[i], &r[i], &y[i]));
int s, g;
assert(2 == scanf("%d%d", &s, &g));
fclose(stdin);
long long result = min_distance(x, h, l, r, y, s, g);
printf("%lld\n", result);
fclose(stdout);
return 0;
}
#endif
Compilation message
walk.cpp: In function 'll min_distance(std::vector<long long int>, std::vector<long long int>, std::vector<long long int>, std::vector<long long int>, std::vector<long long int>, ll, ll)':
walk.cpp:223:5: warning: 'T' may be used uninitialized in this function [-Wmaybe-uninitialized]
223 | if (v == T) return dist[v];
| ^~
/usr/bin/ld: /tmp/ccfsCSde.o: in function `main':
grader.cpp:(.text.startup+0x395): undefined reference to `min_distance(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, int, int)'
collect2: error: ld returned 1 exit status
