#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, s, g;
vector<int> x, h, l, r, y;
struct sky {
int lt, rt, val;
} walk[101010];
bool compare(sky a, sky b) {
if (a.rt == b.rt) return a.lt > b.lt;
return a.rt < b.rt;
}
void sort_end() {
for (int i = 0; i < m; i++) walk[i] = {l[i], r[i], y[i]};
sort(walk, walk + m, compare);
for (int i = 0; i < m; i++) {
l[i] = walk[i].lt;
r[i] = walk[i].rt;
y[i] = walk[i].val;
}
}
vector<int> up, dn;
set< pair<int, int> > pset, mset;
vector<int> add[101010], rem[101010];
void get_updn() {
for (int i = 0; i < m; i++) add[l[i]].push_back(i);
for (int i = 0; i < m; i++) rem[r[i] + 1].push_back(i);
int p = 0;
for (int i = 0; i < m; i++) {
while (p <= r[i]) {
for (int j = 0; j < add[p].size(); j++) {
int tar = add[p][j];
pset.insert({y[tar], tar});
mset.insert({-y[tar], tar});
}
for (int j = 0; j < rem[p].size(); j++) {
int tar = rem[p][j];
pset.erase({y[tar], tar});
mset.erase({-y[tar], tar});
}
p++;
}
if (pset.lower_bound({y[i] + 1, 0}) == pset.end()) up.push_back(-1);
else up.push_back(pset.lower_bound({y[i] + 1, 0})->second);
if (mset.lower_bound({-y[i] + 1, 0}) == mset.end()) dn.push_back(-1);
else dn.push_back(mset.lower_bound({-y[i] + 1, 0})->second);
}
}
vector< pair<int, ll> > adj[101010];
void get_edge() {
for (int i = 0; i < m; i++) {
adj[i].push_back({up[i], y[up[i]] - y[i]});
adj[i].push_back({dn[i], y[i] - y[dn[i]]});
}
for (int i = 0; i < m; i++) {
if (l[i] == 0) adj[m].push_back({i, y[i]});
if (r[i] == n - 1) adj[i].push_back({m + 1, y[i]});
}
}
ll dis[101010];
priority_queue< pair<ll, int> > pq;
void dijkstra() {
for (int i = 0; i <= m + 1; i++) dis[i] = 1e18;
dis[m] = 0;
pq.push({-dis[m], m});
while (!pq.empty()) {
int now = pq.top().second; ll nowdis = -pq.top().first;
pq.pop();
for (int i = 0; i < adj[now].size(); i++) {
int next = adj[now][i].first;
if (dis[next] > nowdis + adj[now][i].second) {
dis[next] = nowdis + adj[now][i].second;
pq.push({-dis[next], next});
}
}
}
}
ll 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) {
x = X; h = H; l = L; r = R; y = Y; s = S; g = G;
n = x.size();
m = l.size();
sort_end();
//for (int i = 0; i < m; i++) cout << l[i] << " " << r[i] << " " << y[i] << "\n";
//cout << "\n";
get_updn();
//for (int i = 0; i < m; i++) cout << up[i] << " ";
//cout << "\n";
//for (int i = 0; i < m; i++) cout << dn[i] << " ";
//cout << "\n";
get_edge();
dijkstra();
ll ans = dis[m + 1];
if (ans >= 1e18) return -1;
ans = ans + x[n - 1] - x[0];
return ans;
}
Compilation message
walk.cpp: In function 'void get_updn()':
walk.cpp:36:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for (int j = 0; j < add[p].size(); j++) {
| ~~^~~~~~~~~~~~~~~
walk.cpp:41:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for (int j = 0; j < rem[p].size(); j++) {
| ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void dijkstra()':
walk.cpp:77:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for (int i = 0; i < adj[now].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
7380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
7380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
13836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
13836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
7380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
