이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
struct Way {
int l;
int r;
int y;
};
struct Tower {
int x;
int y;
};
struct SegTree {
int n;
std::vector<std::vector<std::pair<int, int> > > data;
SegTree (std::vector<int> a) {
for (n = 1; n < (int) a.size(); n <<= 1);
data.resize(n << 1);
for (int i = 0; i < (int) a.size(); i++) data[i + n] = { {a[i], i} };
for (int i = n; --i; ) {
data[i].resize(data[i << 1].size() + data[i << 1 | 1].size());
std::merge(data[i << 1].begin(), data[i << 1].end(), data[i << 1 | 1].begin(), data[i << 1 | 1].end(), data[i].begin());
}
}
std::vector<int> greater_list(int l, int r, int x) {
std::vector<int> res;
auto process = [&] (std::vector<std::pair<int, int> > data) {
for (int i = data.size(); i--; ) {
if (data[i].first < x) break;
res.push_back(data[i].second);
}
};
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (r & 1) process(data[--r]);
if (l & 1) process(data[l++]);
}
return res;
}
};
template<typename T> using pqueue_inv = std::priority_queue<T, std::vector<T>, std::greater<T> >;
long long solve(std::vector<Tower> towers, std::vector<Way> ways, int s, int g) {
int n = towers.size();
if (!s && g == n - 1) {
std::map<int, int> all;
std::map<int, int64_t> forward, back;
all[0] = 1;
forward[0] = 0;
back[0] = 0;
std::vector<int> add[n], remove[n];
for (auto i : ways) {
add[i.l].push_back(i.y);
if (i.r != n - 1) remove[i.r].push_back(i.y);
}
remove[0].push_back(0);
for (int i = 0; i < n; i++) {
for (auto j : add[i]) {
int64_t dist = 1000000000000000000;
auto itr = forward.upper_bound(j);
if (itr != forward.begin()) dist = std::min(dist, std::prev(itr)->second + (j - std::prev(itr)->first));
itr = back.lower_bound(j);
if (itr != back.end()) dist = std::min(dist, itr->second + (itr->first - j));
all[j]++;
itr = forward.upper_bound(j);
if (itr == forward.begin() || (std::prev(itr)->second - std::prev(itr)->first) > dist - j) {
forward[j] = dist;
while (itr != forward.end() && itr->second - itr->first > dist - j) itr = forward.erase(itr);
}
itr = back.lower_bound(j);
if (itr == back.end() || itr->first + itr->second > dist + j) {
back[j] = dist;
while (itr != back.begin() && std::prev(itr)->first + std::prev(itr)->second > dist + j) back.erase(std::prev(itr));
}
}
for (auto j : remove[i]) {
if (all[j] == 1) {
if (forward.count(j)) {
auto itr = all.upper_bound(j);
if (itr != all.end() && !forward.count(itr->first)) forward[itr->first] = forward[j] + (itr->first - j);
forward.erase(j);
}
if (back.count(j)) {
auto itr = all.lower_bound(j);
if (itr != all.begin() && !back.count(std::prev(itr)->first))
back[std::prev(itr)->first] = back[j] + (j - std::prev(itr)->first);
back.erase(j);
}
all.erase(j);
} else all[j]--;
}
}
if (!back.size()) return -1;
int64_t res = back.begin()->second + back.begin()->first;
if (res > 500000000000000000) return -1;
return res + (towers.back().x - towers.front().x);
}
if (towers.size() <= 50 && ways.size() <= 50) {
std::vector<int> ys{0};
for (auto i : ways) ys.push_back(i.y);
std::sort(ys.begin(), ys.end());
ys.erase(std::unique(ys.begin(), ys.end()), ys.end());
auto compress = [&] (int i) { return std::lower_bound(ys.begin(), ys.end(), i) - ys.begin(); };
int h = ys.size();
std::vector<std::pair<int, int> > hen[n * h];
auto add = [&] (int i, int j, int c) {
hen[i].push_back({j, c});
hen[j].push_back({i, c});
};
for (int i = 0; i < n; i++) for (int j = 1; j < h; j++) if (ys[j] <= towers[i].y) add(i * h + j, i * h + j - 1, ys[j] - ys[j - 1]);
for (auto i : ways) {
int cur_h = compress(i.y);
// std::cerr << i.l << "," << i.r << " " << i.y << "->" << cur_h << std::endl;
int last = i.l;
for (int j = i.l; ++j <= i.r; ) {
// std::cerr << " " << towers[j].y << " " << i.y << std::endl;
if (towers[j].y >= i.y) {
// std::cerr << " at " << j << std::endl;
add(last * h + cur_h, j * h + cur_h, towers[j].x - towers[last].x);
last = j;
}
}
}
std::vector<int64_t> dist(n * h, 1000000000000000000);
pqueue_inv<std::pair<int64_t, int> > que;
que.push({dist[s * h] = 0, s * h});
while (que.size()) {
auto i = que.top();
que.pop();
// std::cerr << i.second << " " << i.first << std::endl;
if (i.first != dist[i.second]) continue;
for (auto j : hen[i.second]) if (dist[j.first] > i.first + j.second)
que.push({dist[j.first] = i.first + j.second, j.first});
}
int64_t res = dist[g * h];
if (res > 500000000000000000) return -1;
return res;
} else {
std::vector<int> heights;
for (auto i : towers) heights.push_back(i.y);
SegTree tree(heights);
std::map<int, int> ids[n];
std::vector<int> list[ways.size()];
for (int i = 0; i < (int) ways.size(); i++) {
list[i] = tree.greater_list(ways[i].l, ways[i].r + 1, ways[i].y);
std::sort(list[i].begin(), list[i].end());
for (auto j : list[i]) ids[j][ways[i].y];
}
ids[s][0];
ids[g][0];
struct Hen {
int a;
int b;
int c;
};
std::vector<Hen> hens;
int cnt = 0;
for (int i = 0; i < n; i++) {
int last = -1;
for (auto &j : ids[i]) {
if (last != -1) hens.push_back({cnt - 1, cnt, j.first - last});
last = j.first;
j.second = cnt++;
}
}
for (int i = 0; i < (int) ways.size(); i++) {
int last_x = -1;
int last_id = -1;
for (auto j : list[i]) {
int id = ids[j][ways[i].y];
if (last_x != -1) hens.push_back({last_id, id, towers[j].x - last_x});
last_x = towers[j].x;
last_id = id;
}
}
std::vector<std::pair<int, int> > hen[cnt];
for (auto i : hens) {
hen[i.a].push_back({i.b, i.c});
hen[i.b].push_back({i.a, i.c});
}
std::vector<int64_t> dist(cnt, 1000000000000000000);
pqueue_inv<std::pair<int64_t, int> > que;
que.push({dist[ids[s][0]] = 0, ids[s][0]});
while (que.size()) {
auto i = que.top();
que.pop();
// std::cerr << i.second << " " << i.first << std::endl;
if (i.first != dist[i.second]) continue;
for (auto j : hen[i.second]) if (dist[j.first] > i.first + j.second)
que.push({dist[j.first] = i.first + j.second, j.first});
}
int64_t res = dist[ids[g][0]];
if (res > 500000000000000000) return -1;
return res;
}
assert(0);
return -1;
}
long long min_distance(std::vector<int> a, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
std::vector<Tower> towers;
for (int i = 0; i < (int) a.size(); i++) towers.push_back({a[i], h[i]});
std::vector<Way> ways;
for (int i = 0; i < (int) l.size(); i++) ways.push_back({l[i], r[i], y[i]});
return solve(towers, ways, s, g);
}
/*
int ri() {
int n;
scanf("%d", &n);
return n;
}
int main() {
}
*/
# | 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... |