| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 657693 | evenvalue | Sky Walking (IOI19_walk) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
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 = 1e17 + 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, kInf64);
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 ? h < other.h : l < other.l);
}
};
int64 min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int S, int 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 - X[L[s]]);
add_edge(ends[s].second, v, X[R[s]] - x);
add_edge(u, v, h - Y[s]);
};
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';
}
}
const int64 ans = dijkstra(g, S).first[G];
return (ans == kInf64 ? -1 : ans);
}
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;
}