#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, idx;
} 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;
}
}
set<int> xpset, xmset;
vector< pair< pair<int, int>, int > > points;
vector<int> ylist;
vector<int> add[101010], rem[101010];
bool compval(sky a, sky b) {
return a.val < b.val;
}
void get_points() {
for (int i = 0; i < m; i++) ylist.push_back(walk[i].val);
sort(ylist.begin(), ylist.end());
ylist.erase(unique(ylist.begin(), ylist.end()), ylist.end());
for (int i = 0; i < m; i++) walk[i].idx = i;
sort(walk, walk + m, compval);
for (int i = 0; i < m; i++)
walk[i].val = lower_bound(ylist.begin(), ylist.end(), walk[i].val) - ylist.begin();
for (int i = 0; i < n; i++) {
int idx = upper_bound(ylist.begin(), ylist.end(), h[i]) - ylist.begin();
rem[idx].push_back(i);
}
for (int i = 0; i < n; i++) xpset.insert(i);
for (int i = 0; i < n; i++) xmset.insert(-i);
int p = 0;
for (int i = 0; i < m; i++) {
while (p <= walk[i].val) {
for (int j = 0; j < add[p].size(); j++) {
int tar = add[p][j];
xpset.erase(walk[tar].lt);
xpset.erase(walk[tar].rt);
xmset.erase(-walk[tar].lt);
xmset.erase(-walk[tar].rt);
}
p++;
}
if (walk[i].lt < s && s < walk[i].rt && ylist[walk[i].val] <= h[s]) {
points.push_back({{*xpset.lower_bound(s), ylist[walk[i].val]}, walk[i].idx});
points.push_back({{-*xmset.lower_bound(-s), ylist[walk[i].val]}, walk[i].idx});
}
if (walk[i].lt < g && g < walk[i].rt && ylist[walk[i].val] <= h[g]) {
points.push_back({{*xpset.lower_bound(g), ylist[walk[i].val]}, walk[i].idx});
points.push_back({{-*xmset.lower_bound(-g), ylist[walk[i].val]}, walk[i].idx});
}
points.push_back({{walk[i].lt, ylist[walk[i].val]}, walk[i].idx});
points.push_back({{walk[i].rt, ylist[walk[i].val]}, walk[i].idx});
}
for (int i = 0; i < m; i++) rem[i].clear();
sort(points.begin(), points.end());
points.erase(unique(points.begin(), points.end()), points.end());
}
void print_points() {
for (int i = 0; i < points.size(); i++)
cout << points[i].first.first << " " << points[i].first.second << "\n";
cout << "\n";
}
set< pair<int, int> > pset, mset;
vector< pair< pair<int, int>, int > > vertex;
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 < points.size(); i++) {
int X = points[i].first.first, Y = points[i].first.second, num = points[i].second;
while (p <= X) {
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, num + 1}) == pset.end());
else if (pset.lower_bound({Y, num + 1})->first <= h[X]) vertex.push_back({
{X, pset.lower_bound({Y, num + 1})->first},
pset.lower_bound({Y, num + 1})->second
});
if (mset.lower_bound({-Y, num + 1}) == mset.end());
else vertex.push_back({
{X, -mset.lower_bound({-Y, num + 1})->first},
mset.lower_bound({-Y, num + 1})->second
});
vertex.push_back({{X, Y}, num});
}
for (int i = 0; i < n; i++) add[i].clear();
for (int i = 0; i < n; i++) rem[i].clear();
while (pset.size() > 0) pset.erase(pset.begin());
while (mset.size() > 0) mset.erase(mset.begin());
vertex.push_back({{s, 0}, -1});
vertex.push_back({{g, 0}, -1});
sort(vertex.begin(), vertex.end());
vertex.erase(unique(vertex.begin(), vertex.end()), vertex.end());
}
void print_vertex() {
for (int i = 0; i < vertex.size(); i++)
cout << vertex[i].first.first << " " << vertex[i].first.second << "\n";
cout << "\n";
}
vector< pair<int, ll> > adj[2020202];
void link_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 < points.size(); i++) {
int X = points[i].first.first, Y = points[i].first.second, num = points[i].second;
while (p <= X) {
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++;
}
int now = lower_bound(vertex.begin(), vertex.end(), points[i]) - vertex.begin();
pair< pair<int, int>, int > up, dn;
if (pset.lower_bound({Y, num + 1}) == pset.end());
else if (pset.lower_bound({Y, num + 1})->first <= h[X]) {
up = {
{X, pset.lower_bound({Y, num + 1})->first},
pset.lower_bound({Y, num + 1})->second
};
adj[now].push_back({
lower_bound(vertex.begin(), vertex.end(), up) - vertex.begin(),
up.first.second - Y
});
/*
adj[lower_bound(vertex.begin(), vertex.end(), up) - vertex.begin()].push_back({
now,
up.first.second - Y
});*/
}
if (mset.lower_bound({-Y, num + 1}) == mset.end());
else {
dn = {
{X, -mset.lower_bound({-Y, num + 1})->first},
mset.lower_bound({-Y, num + 1})->second
};
adj[now].push_back({
lower_bound(vertex.begin(), vertex.end(), dn) - vertex.begin(),
points[i].first.second + mset.lower_bound({-Y, num + 1})->first
});
/*
adj[lower_bound(vertex.begin(), vertex.end(), dn) - vertex.begin()].push_back({
now,
points[i].first.second + mset.lower_bound({-Y, num + 1})->first
});*/
}
}
for (int i = 0; i < n; i++) add[i].clear();
for (int i = 0; i < n; i++) rem[i].clear();
while (pset.size() > 0) pset.erase(pset.begin());
while (mset.size() > 0) mset.erase(mset.begin());
}
vector<int> xlist[101010];
void link_walk() {
for (int i = 0; i < vertex.size(); i++) {
if (vertex[i].second >= 0) xlist[vertex[i].second].push_back(vertex[i].first.first);
}
for (int i = 0; i < m; i++) sort(xlist[i].begin(), xlist[i].end());
for (int i = 0; i < m; i++) {
for (int j = 1; j < xlist[i].size(); j++) {
int lt = lower_bound(vertex.begin(), vertex.end(), make_pair(
make_pair(xlist[i][j - 1], y[i]), i
)) - vertex.begin();
int rt = lower_bound(vertex.begin(), vertex.end(), make_pair(
make_pair(xlist[i][j], y[i]), i
)) - vertex.begin();
adj[lt].push_back({rt, x[xlist[i][j]] - x[xlist[i][j - 1]]});
adj[rt].push_back({lt, x[xlist[i][j]] - x[xlist[i][j - 1]]});
}
}
}
void link_sted() {
int st = lower_bound(vertex.begin(), vertex.end(), make_pair(make_pair(s, 0), -1)) - vertex.begin();
for (int i = 0; i < vertex.size(); i++) {
if (vertex[i].first.first == s) {
adj[i].push_back({st, vertex[i].first.second});
adj[st].push_back({i, vertex[i].first.second});
}
}
int ed = lower_bound(vertex.begin(), vertex.end(), make_pair(make_pair(g, 0), -1)) - vertex.begin();
for (int i = 0; i < vertex.size(); i++) {
if (vertex[i].first.first == g) {
adj[i].push_back({ed, vertex[i].first.second});
adj[ed].push_back({i, vertex[i].first.second});
}
}
}
void print_adj() {
for (int i = 0; i < vertex.size(); i++) {
for (int j = 0; j < adj[i].size(); j++) {
cout << vertex[i].first.first << " " << vertex[i].first.second
<< " " << vertex[adj[i][j].first].first.first
<< " " << vertex[adj[i][j].first].first.second
<< " " << adj[i][j].second << "\n";
}
}
}
ll dis[2020202];
priority_queue< pair<ll, int> > pq;
void dijkstra() {
for (int i = 0; i <= 2000000; i++) dis[i] = 1e18;
int st = lower_bound(vertex.begin(), vertex.end(), make_pair(make_pair(s, 0), -1)) - vertex.begin();
dis[st] = 0;
pq.push({-dis[st], st});
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});
}
}
}
}
void print_dis() {
for (int i = 0; i < vertex.size(); i++) {
cout << vertex[i].first.first << " " << vertex[i].first.second << " " << dis[i] << "\n";
}
}
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();
get_points();
//print_points();
get_updn();
//print_vertex();
link_updn();
link_walk();
link_sted();
//print_adj();
dijkstra();
//print_dis();
int ed = lower_bound(vertex.begin(), vertex.end(), make_pair(make_pair(g, 0), -1)) - vertex.begin();
ll ans = dis[ed];
if (ans >= 1e18) return -1;
return ans;
}
Compilation message
walk.cpp: In function 'void get_points()':
walk.cpp:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for (int j = 0; j < add[p].size(); j++) {
| ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void print_points()':
walk.cpp:80:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for (int i = 0; i < points.size(); i++)
| ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void get_updn()':
walk.cpp:92:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for (int i = 0; i < points.size(); i++) {
| ~~^~~~~~~~~~~~~~~
walk.cpp:95:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for (int j = 0; j < add[p].size(); j++) {
| ~~^~~~~~~~~~~~~~~
walk.cpp:100:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for (int j = 0; j < rem[p].size(); j++) {
| ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void print_vertex()':
walk.cpp:132:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
132 | for (int i = 0; i < vertex.size(); i++)
| ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void link_updn()':
walk.cpp:143:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
143 | for (int i = 0; i < points.size(); i++) {
| ~~^~~~~~~~~~~~~~~
walk.cpp:146:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | for (int j = 0; j < add[p].size(); j++) {
| ~~^~~~~~~~~~~~~~~
walk.cpp:151:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
151 | for (int j = 0; j < rem[p].size(); j++) {
| ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void link_walk()':
walk.cpp:202:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
202 | for (int i = 0; i < vertex.size(); i++) {
| ~~^~~~~~~~~~~~~~~
walk.cpp:207:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
207 | for (int j = 1; j < xlist[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~~~
walk.cpp: In function 'void link_sted()':
walk.cpp:222:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
222 | for (int i = 0; i < vertex.size(); i++) {
| ~~^~~~~~~~~~~~~~~
walk.cpp:230:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
230 | for (int i = 0; i < vertex.size(); i++) {
| ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void print_adj()':
walk.cpp:239:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
239 | for (int i = 0; i < vertex.size(); i++) {
| ~~^~~~~~~~~~~~~~~
walk.cpp:240: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]
240 | for (int j = 0; j < adj[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void dijkstra()':
walk.cpp:259: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]
259 | for (int i = 0; i < adj[now].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
walk.cpp: In function 'void print_dis()':
walk.cpp:270:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
270 | for (int i = 0; i < vertex.size(); i++) {
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
70404 KB |
Output is correct |
| 2 |
Correct |
29 ms |
70456 KB |
Output is correct |
| 3 |
Incorrect |
30 ms |
70488 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
70580 KB |
Output is correct |
| 2 |
Correct |
29 ms |
70472 KB |
Output is correct |
| 3 |
Correct |
596 ms |
119840 KB |
Output is correct |
| 4 |
Incorrect |
505 ms |
135088 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
159 ms |
89452 KB |
Output is correct |
| 2 |
Correct |
897 ms |
124592 KB |
Output is correct |
| 3 |
Correct |
962 ms |
129332 KB |
Output is correct |
| 4 |
Correct |
1032 ms |
144936 KB |
Output is correct |
| 5 |
Correct |
1306 ms |
144760 KB |
Output is correct |
| 6 |
Correct |
1234 ms |
144456 KB |
Output is correct |
| 7 |
Correct |
402 ms |
116348 KB |
Output is correct |
| 8 |
Correct |
264 ms |
117940 KB |
Output is correct |
| 9 |
Correct |
1069 ms |
143948 KB |
Output is correct |
| 10 |
Correct |
488 ms |
127520 KB |
Output is correct |
| 11 |
Correct |
52 ms |
77384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
159 ms |
89452 KB |
Output is correct |
| 2 |
Correct |
897 ms |
124592 KB |
Output is correct |
| 3 |
Correct |
962 ms |
129332 KB |
Output is correct |
| 4 |
Correct |
1032 ms |
144936 KB |
Output is correct |
| 5 |
Correct |
1306 ms |
144760 KB |
Output is correct |
| 6 |
Correct |
1234 ms |
144456 KB |
Output is correct |
| 7 |
Correct |
402 ms |
116348 KB |
Output is correct |
| 8 |
Correct |
264 ms |
117940 KB |
Output is correct |
| 9 |
Correct |
1069 ms |
143948 KB |
Output is correct |
| 10 |
Correct |
488 ms |
127520 KB |
Output is correct |
| 11 |
Correct |
52 ms |
77384 KB |
Output is correct |
| 12 |
Correct |
983 ms |
129368 KB |
Output is correct |
| 13 |
Correct |
876 ms |
144784 KB |
Output is correct |
| 14 |
Correct |
1296 ms |
144884 KB |
Output is correct |
| 15 |
Correct |
630 ms |
131636 KB |
Output is correct |
| 16 |
Correct |
703 ms |
137952 KB |
Output is correct |
| 17 |
Correct |
753 ms |
144572 KB |
Output is correct |
| 18 |
Correct |
634 ms |
131764 KB |
Output is correct |
| 19 |
Correct |
698 ms |
137872 KB |
Output is correct |
| 20 |
Correct |
508 ms |
115736 KB |
Output is correct |
| 21 |
Correct |
90 ms |
85336 KB |
Output is correct |
| 22 |
Correct |
544 ms |
131300 KB |
Output is correct |
| 23 |
Correct |
482 ms |
129696 KB |
Output is correct |
| 24 |
Correct |
386 ms |
119736 KB |
Output is correct |
| 25 |
Correct |
437 ms |
126960 KB |
Output is correct |
| 26 |
Correct |
349 ms |
113852 KB |
Output is correct |
| 27 |
Correct |
1366 ms |
145580 KB |
Output is correct |
| 28 |
Correct |
691 ms |
144240 KB |
Output is correct |
| 29 |
Correct |
1305 ms |
144096 KB |
Output is correct |
| 30 |
Correct |
430 ms |
116548 KB |
Output is correct |
| 31 |
Correct |
1139 ms |
144260 KB |
Output is correct |
| 32 |
Correct |
358 ms |
120820 KB |
Output is correct |
| 33 |
Incorrect |
359 ms |
121268 KB |
Output isn't correct |
| 34 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
70404 KB |
Output is correct |
| 2 |
Correct |
29 ms |
70456 KB |
Output is correct |
| 3 |
Incorrect |
30 ms |
70488 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
