이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
struct segtree {
segtree *left, *right;
int value;
segtree(int l, int r) {
if (l == r) {
value = 0;
} else {
value = -1;
int m = (l + r) / 2;
left = new segtree(l, m);
right = new segtree(m + 1, r);
}
}
void push() {
if (value != -1) {
left->value = right->value = value;
value = -1;
}
}
void update(int x, int a, int b, int l, int r) {
if (b < l || r < a) {
return;
} else if (a <= l && r <= b) {
value = x;
} else {
push();
int m = (l + r) / 2;
left->update(x, a, b, l, m);
right->update(x, a, b, m + 1, r);
}
}
int query(int a, int l, int r) {
if (l == r) {
return value;
} else {
push();
int m = (l + r) / 2;
if (a <= m) {
return left->query(a, l, m);
} else {
return right->query(a, m + 1, r);
}
}
}
};
long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
int n = x.size(), m = y.size();
vector<array<int, 3>> events;
for (int i = 0; i < n; ++i) {
events.push_back({h[i], INT_MAX, i});
}
for (int i = 0; i < m; ++i) {
events.push_back({y[i], l[i], r[i]});
}
sort(events.begin(), events.end());
set<int> buildings;
for (int i = 0; i < n; ++i) {
buildings.insert(i);
}
vector<map<int, vector<array<int, 2>>>> adj(n);
segtree *prv = new segtree(0, n - 1);
vector<array<int, 3>> skywalks;
map<int, set<int>> nodes;
for (auto [i, a, b] : events) {
if (a == INT_MAX) {
buildings.erase(b);
} else {
set<int> segments = {a, b};
for (auto j : {s, g}) {
auto it = buildings.lower_bound(j);
if (it != buildings.end()) {
segments.insert(*it);
}
it = buildings.upper_bound(j);
if (it != buildings.begin()) {
segments.insert(*--it);
}
}
while (*segments.begin() < a) {
segments.erase(segments.begin());
}
while (*--segments.end() > b) {
segments.erase(--segments.end());
}
for (auto j : segments) {
int k = prv->query(j, 0, n - 1);
adj[j][k].push_back({j, i});
adj[j][i].push_back({j, k});
nodes[k].insert(j);
nodes[i].insert(j);
}
prv->update(i, a, b, 0, n - 1);
}
}
for (int i = 0; i < m; ++i) {
auto it = nodes[y[i]].lower_bound(l[i]);
while (*it != r[i]) {
auto nxt = it; ++nxt;
adj[*nxt][y[i]].push_back({*it, y[i]});
adj[*it][y[i]].push_back({*nxt, y[i]});
it = nxt;
}
}
priority_queue<tuple<long long, int, int>> dijkstra;
vector<map<int, long long>> dist(n);
dijkstra.push({0, s, 0});
dist[s][0] = 0;
while (!dijkstra.empty()) {
auto [d, i, j] = dijkstra.top();
dijkstra.pop();
d = -d;
if (d > dist[i][j]) {
continue;
}
if (i == g && j == 0) {
return d;
}
for (auto [ic, jc] : adj[i][j]) {
int w = i == ic ? abs(j - jc) : abs(x[i] - x[ic]);
if (dist[ic].count(jc) == 0 || d + w < dist[ic][jc]) {
dijkstra.push({-(d + w), ic, jc});
dist[ic][jc] = d + w;
}
}
}
return -1;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |