// #include "walk.h"
// bruteForce sub 3
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef tuple<int, int, int> tiii;
typedef vector<bool> vb;
typedef vector<ll> vi;
typedef vector<pii> vpii;
typedef vector<tiii> vtiii;
typedef vector<vi> vvi;
typedef vector<vpii> vvpii;
#define F0R(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
const int maxN = 10005;
const ll INF = 1e18;
ll min_distance(vpii &B, vtiii &S, int s, int g) {
int n = sz(B);
int m = sz(S);
map<ll, ll> dp;
dp[0] = 0;
priority_queue<pii, vpii, greater<pii>> q;
F0R(i, m) q.push({get<0>(S[i]), -(i + 1)});
S.push_back({0, 0, 0});
q.push({0, m + 1});
set<ll> ignore;
while (!q.empty()) {
if (sz(dp) == 0) return -1;
int l, r, y, i, idx;
tie(l, i) = q.top();
q.pop();
if (l >= g) break;
idx = abs(i) - 1;
tie(l, r, y) = S[idx];
if (idx > i) { // hinzufügen
auto it = dp.lower_bound(y);
if (it->first == y) {
ignore.insert(y);
} else {
ll v = INF;
if (it != dp.end()) {
v = min(v, it->second + abs(it->first - y));
}
if (it != dp.begin()) {
--it;
v = min(v, it->second + abs(it->first - y));
}
dp[y] = v;
}
q.push({r, idx + 1});
} else { // Entfernen
auto iti = ignore.find(idx);
if (iti == ignore.end()) { // die Linie wird nicht fortgeführt
auto it = dp.find(y);
ll yy,dd; tie(yy,dd) = *it;
if (it != dp.begin()) {
--it;
it->second = min(it->second, dd + abs(it->first - yy));
++it;
}
++it;
if (it != dp.end()) {
it->second = min(it->second, dd + abs(it->first - yy));
}
--it;
dp.erase(it);
} else {
ignore.erase(iti);
}
}
}
ll ans = INF;
for (auto it = dp.begin(); it != dp.end(); ++it) {
ans = min(ans, it->second + it->first);
}
return ans + B[g].first - B[s].first;
}
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 s,
int g) {
// ll min_distance(vi x, vi h, vi l, vi r, vi y, int s, int g) {
int n = sz(x), m = sz(l);
if (g < s) swap(g, s);
vtiii segs(m);
vpii B(n);
F0R(i, n) B[i] = {x[i], h[i]};
F0R(i, m) segs[i] = {l[i], r[i], y[i]};
return min_distance(B, segs, s, g);
}
int main() {
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;
}
Compilation message
walk.cpp: In function 'll min_distance(vpii&, vtiii&, int, int)':
walk.cpp:24:9: warning: unused variable 'n' [-Wunused-variable]
24 | int n = sz(B);
| ^
/usr/bin/ld: /tmp/cc85sFSP.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccSA2odO.o:walk.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
