#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 6e5+10;
const ll INF = 1e18+10;
template <class T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;
int n, m;
vector<pair<int, ll>> adj[N];
ll dist[N], extra[N]; // extra cost for the nodes
void add_edge(int a, int b, ll w) {
// cerr << "add: " << a << ' ' << b << ' ' << w << endl;
adj[a].emplace_back(b, w);
adj[b].emplace_back(a, w);
}
void dijkstra(int S) {
fill(dist, dist + N, INF);
for (int a = 0; a < N; a++) {
for (auto& [b, w] : adj[a]) {
w += extra[b];
}
}
min_pq<pair<ll, int>> pq;
pq.push({dist[S] = 0, S});
while (!pq.empty()) {
auto [d_c, c] = pq.top(); pq.pop();
if (dist[c] != d_c) continue;
for (auto [nxt, w] : adj[c]) {
if (dist[nxt] > dist[c] + w) {
dist[nxt] = dist[c] + w;
pq.push({dist[nxt], nxt});
}
}
}
}
long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
n = sz(x), m = sz(l);
vector<int> nl, nr, ny;
for (int i = 0; i < m; i++) {
if (l[i] < s && r[i] > s) {
bool has = 0;
for (int j = s; j <= g; j++) if (h[j] >= y[i]) {
has = 1;
}
if (!has) {
int one = s;
int two = g;
while (h[one] < y[i]) one--;
while (h[two] < y[i]) two++;
l[i] = one, r[i] = two;
extra[sz(nl)] += x[s] - x[l[i]] + x[r[i]] - x[g];
nl.push_back(l[i]);
nr.push_back(r[i]);
ny.push_back(y[i]);
continue;
}
}
if (l[i] < s && r[i] >= s) {
int one = s-1;
while (one >= l[i] && h[one] < y[i]) one--;
int two = s;
while (two <= r[i] && h[two] < y[i]) two++;
// [l, one]
// [one, two] -> extra of x[s] - x[one]
// l[i] = two
// cerr << "> " << one << ' ' << l[i] << ' ' << two << endl;
if (l[i] < one) { nl.push_back(l[i]); nr.push_back(one); ny.push_back(y[i]); }
if (one < two && two <= r[i]) {
// cerr << "extra: " << sz(nl) << ' ' << x[s] - x[one] << endl;
extra[sz(nl)] += x[s] - x[one];
nl.push_back(one); nr.push_back(two); ny.push_back(y[i]);
}
l[i] = two;
}
if (r[i] > g && l[i] <= g) {
int one = g+1;
while (one <= r[i] && h[one] < y[i]) one++;
int two = g;
while (two >= l[i] && h[two] < y[i]) two--;
// [one, r]
// [two, one] -> extra of x[one] - x[g]
// r[i] = two
if (one < r[i]) { nl.push_back(one); nr.push_back(r[i]); ny.push_back(y[i]); }
if (two < one && two >= l[i]) {
extra[sz(nl)] += x[one] - x[g];
nl.push_back(two), nr.push_back(one), ny.push_back(y[i]);
}
r[i] = two;
}
if (l[i] < r[i]) {
nl.push_back(l[i]);
nr.push_back(r[i]);
ny.push_back(y[i]);
}
}
// cout << sz(l) << ' ' << sz(r) << ' ' << sz(y) << endl;
swap(l, nl); swap(r, nr); swap(y, ny);
// cout << sz(l) << ' ' << sz(r) << ' ' << sz(y) << endl;
m = sz(l);
// for (int i = 0; i < m; i++) {
// cerr << l[i] << ' ' << r[i] << ' ' << y[i] << ' ' << extra[i] << endl;
// }
// s = 0;
auto build = [&]() {
vector<vector<int>> ev(n);
for (int i = 0; i < m; i++) {
ev[l[i]].push_back(i);
ev[r[i]].push_back(i);
}
vector<bool> on(m);
set<pair<int, int>> s;
for (int i = 0; i < n; i++) {
for (int x : ev[i]) if (!on[x]) {
auto me = s.insert({y[x], x}).first;
if (y[x] <= h[i]) {
auto it = next(me);
while (true) {
if (it != s.end() && it->first <= h[i]) {
// cerr << "h1\n";
add_edge(x, it->second, it->first - y[x]);
} else break;
it = next(it);
}
}
if (y[x] <= h[i]) {
if (me != s.begin()) {
auto it = prev(me);
// cerr << "h2\n";
while (true) {
add_edge(x, it->second, y[x] - it->first);
if (it == s.begin()) break;
it = prev(it);
}
}
}
}
for (int x : ev[i]) if (on[x]) {
auto me = s.find({y[x], x});
if (y[x] <= h[i]) {
auto it = next(me);
while (true) {
if (it != s.end() && it->first <= h[i]) {
// cerr << "h3\n";
add_edge(x, it->second, it->first - y[x]);
} else break;
it = next(it);
}
}
if (y[x] <= h[i]) {
if (me != s.begin()) {
// cerr << "h3\n";
auto it = prev(me);
while (true) {
add_edge(x, it->second, y[x] - it->first);
if (it == s.begin()) break;
it = prev(it);
}
}
}
s.erase(me);
}
for (int x : ev[i]) on[x] = !on[x];
}
};
build();
int S = m;
for (int i = 0; i < m; i++) {
// cerr << "> " << l[i] << ' ' << s << ' ' << r[i] << ' ' << y[i] << ' ' << h[s] << endl;
if (l[i] <= s && s <= r[i] && y[i] <= h[s]) {
add_edge(S, i, y[i]);
}
}
dijkstra(S);
ll ans = INF;
for (int i = 0; i < m; i++) {
if (l[i] <= g && g <= r[i] && y[i] <= h[g]) {
ans = min(ans, dist[i] + y[i]);
}
}
// cerr << "base: " << ans << endl;
// cerr << x[n-1] - x[0] << ' ' << ans << endl;
if (ans == INF) return -1;
return ans + x[g] - x[s];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
19028 KB |
Output is correct |
| 2 |
Correct |
10 ms |
19028 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
19028 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
19096 KB |
Output is correct |
| 2 |
Correct |
10 ms |
19028 KB |
Output is correct |
| 3 |
Incorrect |
814 ms |
643476 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
96 ms |
54744 KB |
Output is correct |
| 2 |
Runtime error |
1494 ms |
1048576 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
96 ms |
54744 KB |
Output is correct |
| 2 |
Runtime error |
1494 ms |
1048576 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
19028 KB |
Output is correct |
| 2 |
Correct |
10 ms |
19028 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
19028 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
