// #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, pii> dp; // höhe : { value, expiryDate }
dp[0] = {0, n - 1};
sort(all(S), [&](tiii &a, tiii &b) {
if (get<1>(a) != get<1>(b)) return get<1>(a) > get<1>(b);
return get<2>(a) < get<2>(b);
});
int i = 0;
while (i < m) {
tiii seg = S[i];
if (sz(dp) == 0) return -1;
int l, r, y, idx;
tie(l, r, y) = seg;
ll d = INF;
// Oberhalb:
auto ito = dp.lower_bound(y);
if (ito != dp.end()) {
if (ito->second.second > r) {
dp.erase(ito);
continue;
}
d = min(d, ito->second.first + abs(ito->first - y));
}
// Unterhalb:
auto itu = dp.lower_bound(y);
if (itu != dp.begin()) {
--itu;
if (itu->second.second > r) {
dp.erase(itu);
continue;
}
d = min(d, itu->second.first + abs(itu->first - y));
}
// Antwort eintragen
dp[y] = {d, l};
++i;
}
ll ans = INF;
for (auto it = dp.begin(); it != dp.end(); ++it) {
if (it->second.second > B[s].first) continue;
ans = min(ans, it->second.first + 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:38:22: warning: unused variable 'idx' [-Wunused-variable]
38 | int l, r, y, idx;
| ^~~
/usr/bin/ld: /tmp/cc8M08xY.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc6B3IAZ.o:walk.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
