#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;
using int64 = long long;
using ld = long double;
constexpr int kInf = 1e9 + 10;
constexpr int64 kInf64 = 1e15 + 10;
constexpr int kMod = 1e9 + 7;
class LazySegTree {
const int n;
vector<int> t;
void push(const int x, const int l, const int r) {
if (t[x] == -1) return;
const int mid = (l + r) / 2;
const int y = 2 * (mid - l + 1) + x;
for (const int child : {x + 1, y}) {
t[child] = t[x];
}
t[x] = -1;
}
void update(const int x, const int l, const int r, const int ql, const int qr, const int i) {
if (ql <= l and r <= qr) {
t[x] = i;
return;
}
push(x, l, r);
const int mid = (l + r) / 2;
const int y = 2 * (mid - l + 1) + x;
if (ql <= mid) {
update(x + 1, l, mid, ql, qr, i);
}
if (mid < qr) {
update(y, mid + 1, r, ql, qr, i);
}
}
int query(const int x, const int l, const int r, const int p) {
if (l == r) {
return t[x];
}
push(x, l, r);
const int mid = (l + r) / 2;
const int y = 2 * (mid - l + 1) + x;
if (p <= mid) {
return query(x + 1, l, mid, p);
} else {
return query(y, mid + 1, r, p);
}
}
public:
explicit LazySegTree(const int n) : n(n), t(2 * n - 1, -1) {}
void update(const int l, const int r, const int i) {
update(0, 0, n - 1, l, r, i);
}
int query(const int p) {
return query(0, 0, n - 1, p);
}
};
pair<vector<int64>, vector<int>> dijkstra(const vector<vector<pair<int, int>>> &g, const int s) {
const int n = (int) g.size();
vector<int64> d(n, kInf);
vector<int> p(n, -1);
min_heap<pair<int64, int>> q;
d[s] = 0;
q.push({0, s});
while (not q.empty()) {
const auto [dist, x] = q.top();
q.pop();
if (d[x] < dist) continue;
for (const auto &[y, w] : g[x]) {
if (d[y] <= d[x] + w) continue;
d[y] = d[x] + w;
p[y] = x;
q.push({d[y], y});
}
}
return make_pair(d, p);
}
struct building {
int x;
int h;
};
struct skywalk {
int i;
int l;
int r;
int h;
bool operator<(const skywalk &other) const {
return h < other.h;
}
};
int64 min_distance(vector<int32_t> X, vector<int32_t> H, vector<int32_t> L, vector<int32_t> R, vector<int32_t> Y, int32_t S, int32_t G) {
const int n = X.size();
const int m = L.size();
vector<building> buildings(n);
for (int i = 0; i < n; i++) {
buildings[i].h = H[i];
buildings[i].x = X[i];
}
vector<skywalk> skywalks(m);
for (int j = 0; j < m; j++) {
skywalks[j].i = j;
skywalks[j].l = X[L[j]];
skywalks[j].r = X[R[j]];
skywalks[j].h = Y[j];
}
sort(skywalks.begin(), skywalks.end());
vector<vector<pair<int, int>>> g(n);
vector<pair<int, int>> ends(m);
LazySegTree st(n);
auto add_node = [&]() -> int {
g.emplace_back();
return g.size() - 1;
};
auto add_edge = [&](const int x, const int y, const int w) -> void {
g[x].emplace_back(y, w);
g[y].emplace_back(x, w);
};
auto add_vert = [&](const int i, const int h, const int u) {
const int x = X[i];
const int s = st.query(i);
if (s == -1) {
add_edge(u, i, h);
return;
}
const int v = add_node();
add_edge(ends[s].first, v, x - skywalks[s].l);
add_edge(ends[s].second, v, skywalks[s].r - x);
add_edge(u, v, h - skywalks[s].h);
};
for (const skywalk s : skywalks) {
const int i = s.i;
const int l = s.l;
const int r = s.r;
const int h = s.h;
ends[i].first = add_node();
ends[i].second = add_node();
add_edge(ends[i].first, ends[i].second, r - l);
add_vert(L[i], h, ends[i].first);
add_vert(R[i], h, ends[i].second);
st.update(L[i], R[i], i);
}
for (int x = 0; x < g.size(); x++) {
for (const auto &[y, w] : g[x]) {
// cout << x << ' ' << y << ' ' << w << '\n';
}
}
return dijkstra(g, S).first[G];
}
Compilation message
walk.cpp: In function 'int64 min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int32_t, int32_t)':
walk.cpp:182:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
182 | for (int x = 0; x < g.size(); x++) {
| ~~^~~~~~~~~~
walk.cpp:183:22: warning: unused structured binding declaration [-Wunused-variable]
183 | for (const auto &[y, w] : g[x]) {
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4125 ms |
627504 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4109 ms |
525712 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4075 ms |
556840 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4075 ms |
556840 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4125 ms |
627504 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
