#include "walk.h"
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <iostream>
using namespace std;
vector<pair<int, int>> g[1 << 21];
vector<long long> dp(1 << 21, -1);
long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int e) {
int n = x.size();
int m = l.size();
int sz = n - 1;
vector<pair<int, int>> add, now;
set<int> is;
map<int, int> can[n];
for (int i = 0; i < m; ++i)
add.push_back({y[i], i});
for (int i = 0; i < n; ++i)
now.push_back({h[i], i});
sort(add.begin(), add.end());
reverse(add.begin(), add.end());
sort(now.begin(), now.end());
for (int i = 0; i < m; ++i) {
int j = add[i].second;
while (now.size() && now.back().first >= add[i].first) {
is.insert(now.back().second);
now.pop_back();
}
auto it = is.lower_bound(l[j]);
if (!can[l[j]].count(y[j]))
can[l[j]][y[j]] = ++sz;
if (!can[r[j]].count(y[j]))
can[r[j]][y[j]] = ++sz;
int bg = can[l[j]][y[j]];
int ed = can[r[j]][y[j]];
g[bg].push_back({ed, x[r[j]] - x[l[j]]});
g[ed].push_back({bg, x[r[j]] - x[l[j]]});
continue;
while (it != is.end() && *it <= r[j]) {
if (!can[*it].count(y[j]))
can[*it][y[j]] = ++sz;
if (it != is.begin() && *prev(it) >= l[j]) {
g[can[*it][y[j]]].push_back({can[*prev(it)][y[j]], x[*it] - x[*prev(it)]});
g[can[*prev(it)][y[j]]].push_back({can[*it][y[j]], x[*it] - x[*prev(it)]});
}
it = next(it);
}
}
for (int i = 0; i < n; ++i) {
int last = 0, pos = i;
for (auto it = can[i].begin(); it != can[i].end(); ++it) {
g[pos].push_back({it->second, it->first - last});
g[it->second].push_back({pos, it->first - last});
last = it->first;
pos = it->second;
}
}
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;
q.push({0, s});
dp[s] = 0;
while (!q.empty()) {
int v = q.top().second;
long long C = q.top().first;
q.pop();
if (dp[v] < C)
continue;
for (auto [to, c] : g[v]) {
if (dp[to] == -1 || dp[to] > dp[v] + c) {
dp[to] = dp[v] + c;
q.push({dp[to], to});
}
}
}
return dp[e];
}
Compilation message
walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:71:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
71 | for (auto [to, c] : g[v]) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
65856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
65948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
150 ms |
74068 KB |
Output is correct |
| 2 |
Incorrect |
435 ms |
91524 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
150 ms |
74068 KB |
Output is correct |
| 2 |
Incorrect |
435 ms |
91524 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
65856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
