#include "walk.h"
#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
struct SegTree {
int n, N;
vi tree;
int def = LLONG_MAX / 2;
SegTree(vi values) {
n = values.size();
N = 1;
while (N < n) N *= 2;
tree = vi(2 * N, def);
loop(i, n) {
tree[N + i] = values[i];
}
for (int i = N - 1; i >= 1; i--) {
tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
}
}
int merge(int a, int b) {
return min(a, b);
}
void set(int idx, int v) {
idx += N;
tree[idx] = v;
idx /= 2;
while (idx) {
tree[idx] = merge(tree[idx * 2], tree[idx * 2 + 1]);
idx /= 2;
}
}
int get(int l, int r, int i = 1, int tl = 0, int tr = -1) {
if (tr == -1) {
tr = N;
}
if (tr <= l || tl >= r) {
return def;
}
if (tl >= l && tr <= r) {
return tree[i];
}
int tm = (tl + tr) / 2;
return merge(get(l, r, i * 2, tl, tm), get(l, r, i * 2 + 1, tm, tr));
}
};
long long min_distance(std::vector<signed> xs, std::vector<signed> hs, std::vector<signed> ls, std::vector<signed> rs, std::vector<signed> ys, signed s, signed g) {
int n = xs.size();
int m = ls.size();
vector<tuple<int, int, int>> bridges(m);
loop(i, m) {
bridges[i] = { ys[i], ls[i], rs[i] };
}
sort(all(bridges));
vii buildings(n);
loop(i, n) {
buildings[i] = { xs[i], hs[i] };
}
sort(all(buildings));
sort(all(ys));
SegTree minCost(vi(m, LLONG_MAX / 2));
SegTree minCostMinusHeight(vi(m, LLONG_MAX / 2));
vvii open(n), close(n);
loop(i, m) {
auto [y, l, r] = bridges[i];
open[l].push_back({y, i});
close[r].push_back({y, i});
}
loop(i, n) {
sort(all(open[i]));
sort(all(close[i]));
}
for (auto [y, j] : open[0]) {
minCost.set(j, ys[j]);
minCostMinusHeight.set(j, 0);
}
for (int i = 1; i < n; i++) {
int upper = upper_bound(all(ys), buildings[i].second) - ys.begin();
for (auto [y, j] : open[i]) {
int newCost = min(minCostMinusHeight.get(0, j) + y, minCost.get(j + 1, upper));
minCost.set(j, newCost);
minCostMinusHeight.set(j, newCost - y);
}
if (i == n - 1) {
return minCost.get(0, m) * 2LL + int(xs[g]) - int(xs[s]);
}
for (auto [y, j] : close[i]) {
minCost.set(j, LLONG_MAX / 2);
minCostMinusHeight.set(j, LLONG_MAX / 2);
}
}
return 0;
}
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:18:13: error: expected primary-expression before 'long'
18 | #define int long long
| ^~~~
walk.cpp:132:43: note: in expansion of macro 'int'
132 | return minCost.get(0, m) * 2LL + int(xs[g]) - int(xs[s]);
| ^~~
walk.cpp:132:42: error: expected ';' before 'long'
132 | return minCost.get(0, m) * 2LL + int(xs[g]) - int(xs[s]);
| ^
| ;
walk.cpp:18:13: error: expected primary-expression before 'long'
18 | #define int long long
| ^~~~
walk.cpp:132:43: note: in expansion of macro 'int'
132 | return minCost.get(0, m) * 2LL + int(xs[g]) - int(xs[s]);
| ^~~
