#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int inf = 1e9;
long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
int n = x.size(), m = l.size();
vector<pair<int, pair<int, int>>> a, b, c;
for (int i = 0; i < m; i++) a.push_back({ y[i], {l[i], r[i]} });
sort(a.begin(), a.end());
vector<pair<int, int>> bld;
for (int i = 0; i < m; i++) bld.push_back({ h[i], i });
bld.push_back({ 0, -1 }); // just for the sake of it
sort(bld.begin(), bld.end());
{
int rght = inf;
for (int i = n - 1; i >= 0; i--) {
while (a.size() && a.back().first > bld[i].first) {
if (rght != inf && a.back().second.first < rght && a.back().second.second > rght) {
b.push_back({ a.back().first, {a.back().second.first, rght } });
b.push_back({ a.back().first, {rght, a.back().second.second } });
}
else b.push_back(a.back());
a.pop_back();
}
if (bld[i].second >= s)
rght = min(rght, bld[i].second);
}
swap(a, b); reverse(a.begin(), a.end());
}
// {
// int lft = -inf;
// for (int i = n - 1; i >= 0; i--) {
// while (lft != -inf && a.size() && a.back().first > bld[i].first) {
// if (a.back().second.first < lft && a.back().second.second > lft) {
// b.push_back({ a.back().first, {a.back().second.first, lft } });
// b.push_back({ a.back().first, {lft, a.back().second.second } });
// }
// else b.push_back(a.back());
// a.pop_back();
// }
// if (bld[i].second <= s)
// lft = max(lft, bld[i].second);
// }
// swap(a, b); reverse(a.begin(), a.end());
// }
// {
// int rght = inf;
// for (int i = n - 1; i >= 0; i--) {
// while (a.size() && a.back().first > bld[i].first) {
// if (rght != inf && a.back().second.first < rght && a.back().second.second > rght) {
// b.push_back({ a.back().first, {a.back().second.first, rght } });
// b.push_back({ a.back().first, {rght, a.back().second.second } });
// }
// else b.push_back(a.back());
// a.pop_back();
// }
// if (bld[i].second >= g)
// rght = min(rght, bld[i].second);
// }
// swap(a, b); reverse(a.begin(), a.end());
// }
// {
// int lft = -inf;
// for (int i = n - 1; i >= 0; i--) {
// while (a.size() && a.back().first > bld[i].first) {
// if (lft != -inf && a.back().second.first < lft && a.back().second.second > lft) {
// b.push_back({ a.back().first, {a.back().second.first, lft } });
// b.push_back({ a.back().first, {lft, a.back().second.second } });
// }
// else b.push_back(a.back());
// a.pop_back();
// }
// if (bld[i].second <= g)
// lft = max(lft, bld[i].second);
// }
// swap(a, b); reverse(a.begin(), a.end());
// }
reverse(a.begin(), a.end());
set<pair<int, int>> pts; // set of points
map<pair<int, int>, vector<pair<int, int>>> adj;
auto edge = [&](pair<int, int> a, pair<int, int> b) {
adj[a].push_back(b); adj[b].push_back(a);
};
auto dist = [&](pair<int, int> a, pair<int, int> b) -> ll {
return (ll)(abs(x[a.first] - x[b.first]) + abs(a.second - b.second));
};
for (auto& x : a) {
//cout << x.first << "," << x.second.first << "," << x.second.second << endl;
int prev = x.second.first;
auto pt = pts.lower_bound({ x.second.first, 0 });
while (pt != pts.end() && pt->first <= x.second.second) {
edge({ pt->first, x.first }, { prev, x.first });
edge({ pt->first, x.first }, { pt->first, pt->second });
prev = pt->first;
pts.erase(pt++);
}
edge({ x.second.second, x.first }, { prev, x.first });
pts.insert({ x.second.first, x.first });
pts.insert({ x.second.second, x.first });
}
for (auto& x : pts) {
edge({ x.first, x.second }, { x.first, 0 });
}
map<pair<int, int>, ll> dst;
set<pair<ll, pair<int, int>>> q;
q.insert({ 1, {s, 0} });
while (!q.empty()) {
auto t = *q.begin();
q.erase(q.begin());
if (dst[t.second]) continue;
// cout << t.first << "," << t.second.first << "," << t.second.second << endl;
dst[t.second] = t.first;
for (auto& x : adj[t.second]) {
//cout << "bruh" << endl;
q.insert({ dist(t.second, x) + t.first, x });
}
}
//construct & run dijkstra
return dst[{g, 0}] - 1;
}
long long min_distance_stress(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) { // basically dijkstra
int n = x.size(), m = l.size();
map<pair<int, int>, ll> dist;
set<pair<ll, pair<int, int>>> ss;
ss.insert({ 1, {s, 0} });
while (ss.size()) {
auto t = *ss.begin();
ss.erase(ss.begin());
int tim = t.first, xx = t.second.first, yy = t.second.second;
if (dist[t.second]) continue;
//cout << xx << "," << yy << "," << tim << endl;
dist[t.second] = t.first;
for (int i = 0; i < m; i++) {
for (int x2 = 0; x2 < n; x2++) {
if (y[i] == yy && l[i] <= x2 && r[i] >= x2 && l[i] <= xx && r[i] >= xx && h[x2] >= y[i]) ss.insert({ tim + abs(x[x2] - x[xx]), {x2, yy} });
}
if (l[i] <= xx && r[i] >= xx && h[xx] >= y[i]) ss.insert({ tim + abs(y[i] - yy), {xx, y[i]} });
ss.insert({ tim + yy, {xx, 0} });
}
}
return dist[{g, 0}] - 1;
}
// int main() {
// cout << min_distance_stress({ 0, 3, 5, 7, 10, 12, 14 },
// { 8, 7, 9, 7, 6, 6, 9 },
// { 0, 0, 0, 2, 2, 3, 4 },
// { 1, 2, 6, 3, 6, 4, 6 },
// { 1, 6, 8, 1, 7, 2, 5 },
// 1, 5) << endl;
// cout << min_distance({ 0, 3, 5, 7, 10, 12, 14 },
// { 8, 7, 9, 7, 6, 6, 9 },
// { 0, 0, 0, 2, 2, 3, 4 },
// { 1, 2, 6, 3, 6, 4, 6 },
// { 1, 6, 8, 1, 7, 2, 5 },
// 1, 5) << endl;
// }
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
128 ms |
19716 KB |
Output is correct |
| 2 |
Correct |
1429 ms |
77508 KB |
Output is correct |
| 3 |
Correct |
1311 ms |
79712 KB |
Output is correct |
| 4 |
Correct |
1717 ms |
81148 KB |
Output is correct |
| 5 |
Correct |
1837 ms |
84648 KB |
Output is correct |
| 6 |
Correct |
1791 ms |
78552 KB |
Output is correct |
| 7 |
Correct |
590 ms |
43084 KB |
Output is correct |
| 8 |
Correct |
643 ms |
71760 KB |
Output is correct |
| 9 |
Correct |
1494 ms |
75536 KB |
Output is correct |
| 10 |
Correct |
443 ms |
62324 KB |
Output is correct |
| 11 |
Runtime error |
11 ms |
2728 KB |
Execution killed with signal 11 |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
128 ms |
19716 KB |
Output is correct |
| 2 |
Correct |
1429 ms |
77508 KB |
Output is correct |
| 3 |
Correct |
1311 ms |
79712 KB |
Output is correct |
| 4 |
Correct |
1717 ms |
81148 KB |
Output is correct |
| 5 |
Correct |
1837 ms |
84648 KB |
Output is correct |
| 6 |
Correct |
1791 ms |
78552 KB |
Output is correct |
| 7 |
Correct |
590 ms |
43084 KB |
Output is correct |
| 8 |
Correct |
643 ms |
71760 KB |
Output is correct |
| 9 |
Correct |
1494 ms |
75536 KB |
Output is correct |
| 10 |
Correct |
443 ms |
62324 KB |
Output is correct |
| 11 |
Runtime error |
11 ms |
2728 KB |
Execution killed with signal 11 |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
