#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using pll = pair<ll, ll>;
#define X first
#define Y second
struct skywalk {
int l, r, y;
skywalk(int l, int r, int y) {
this->l = l;
this->r = r;
this->y = y;
}
};
int n;
vector<skywalk> S;
int maxv[20][100007];
map<ii, int> M;
int cnt;
vector<ii> G[600007];
void init_maxv(vector<int> &h) {
for(int i = 0 ; i < n ; i++)
maxv[0][i] = h[i];
for(int k = 1 ; k < 19 ; k++)
for(int i = 0 ; i < n ; i++)
maxv[k][i] = max(maxv[k - 1][i], i + (1 << (k - 1)) < n ? maxv[k - 1][i + (1 << (k - 1))] : 0);
}
int first_right(int x, int h) {
int p = x - 1;
for(int k = 18 ; k >= 0 ; k--)
if(maxv[k][p + 1] < h)
p += (1 << k);
return p + 1;
}
int first_left(int x, int h) {
int p = x + 1;
for(int k = 18 ; k >= 0 ; k--)
if(p - (1 << k) >= 0 && maxv[k][p - (1 << k)] < h)
p -= (1 << k);
return p - 1;
}
void reduce(int w) {
vector<skywalk> SP;
for(auto s : S) {
if(s.l <= w && s.r >= w) {
int a = first_left(w, s.y);
int b = first_right(w, s.y);
if(s.l < a)
SP.emplace_back(s.l, a, s.y);
if(a < b)
SP.emplace_back(a, b, s.y);
if(b < s.r)
SP.emplace_back(b, s.r, s.y);
} else {
SP.push_back(s);
}
}
swap(S, SP);
}
void build_graph(vector<int> &x, vector<int> &h) {
multiset<int> active;
vector<ii> E;
map<int, int> lasti;
set<ii> ready;
for(auto s : S) {
E.emplace_back(s.l, -s.y);
E.emplace_back(s.r, s.y);
}
sort(E.begin(), E.end());
int ind = 0;
for(int i = 0 ; i < x.size() ; i++) {
vector<int> interesting;
int ind2 = ind;
while(ind < E.size() && E[ind].X == i && E[ind].Y < 0) {
active.insert(-E[ind].Y);
ind++;
}
while(ind2 < E.size() && E[ind2].X == i) {
int y = abs(E[ind2].Y);
if(ready.count({i, y}) == 0) {
interesting.push_back(y);
ready.insert({i, y});
if(M.count({i, y}) == 0)
M[{i, y}] = ++cnt;
auto it = active.lower_bound(y);
int y2 = 0;
if(it != active.begin())
y2 = *(prev(it));
if(M.count({i, y2}) == 0) {
M[{i, y2}] = ++cnt;
interesting.push_back(y2);
}
//~ cout << i << " " << y << " " << y2 << endl;
int w = M[{i, y}];
int u = M[{i, y2}];
G[w].emplace_back(u, y - y2);
G[u].emplace_back(w, y - y2);
}
ind2++;
}
for(int y : interesting) {
//~ cout << "active: " << i << " " << y << " " << lasti[y] << endl;
if(active.count(y) && lasti.count(y) > 0 && lasti[y] != -1 && lasti[y] < i) {
int pi = lasti[y];
if(M.count({i, y}) == 0)
M[{i, y}] = ++cnt;
if(M.count({pi, y}) == 0)
M[{pi, y}] = ++cnt;
int w = M[{i, y}];
int u = M[{pi, y}];
int d = x[i] - x[pi];
G[w].emplace_back(u, d);
G[u].emplace_back(w, d);
}
lasti[y] = i;
}
while(ind < E.size() && E[ind].X == i && E[ind].Y > 0) {
active.erase(active.find(E[ind].Y));
if(active.count(E[ind].Y) == 0)
lasti[E[ind].Y] = -1;
ind++;
}
}
}
void print_graph() {
cout << cnt << " vertices:" << endl;
for(auto p : M)
cout << p.X.X << "," << p.X.Y << " -> " << p.Y << endl;
cout << "edges:" << endl;
for(int i = 1 ; i <= cnt ; i++) {
cout << i << ": ";
for(ii p : G[i])
cout << "(" << p.X << ","<<p.Y <<") ";
cout << endl;
}
}
ll dist[600007];
ll find_dist(int s, int g) {
int w = M[{s, 0}];
if(!w || !M[{g, 0}])
return -1;
for(int i = 1 ; i <= cnt ; i++)
dist[i] = 1e18;
dist[w] = 0;
//~ cout << w << endl;
set<pll> S;
S.insert({dist[w], w});
while(!S.empty()) {
auto p = *S.begin();
S.erase(S.begin());
for(auto p2 : G[p.Y]) {
if(dist[p2.X] > dist[p.Y] + p2.Y) {
S.erase((pll){dist[p2.X], p2.X});
dist[p2.X] = dist[p.Y] + p2.Y;
S.insert((pll){dist[p2.X], p2.X});
}
}
}
//~ for(int i = 1 ; i <= cnt ; i++)
//~ cout << i << ": " << dist[i] << endl;
return (dist[M[{g, 0}]] < ll(1e18)) ? dist[M[{g, 0}]] : -1;
}
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) {
n = x.size();
init_maxv(h);
for(int i = 0 ; i < (int)l.size() ; i++)
S.emplace_back(l[i], r[i], y[i]);
reduce(s);
reduce(g);
//~ for(auto s : S)
//~ cout << s.l << " " << s.r << " " << s.y << endl;
//~ cout << "####################" << endl;
build_graph(x, h);
//~ print_graph();
return find_dist(s, g);
}
Compilation message
walk.cpp: In function 'void build_graph(std::vector<int>&, std::vector<int>&)':
walk.cpp:88:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < x.size() ; i++) {
~~^~~~~~~~~~
walk.cpp:92:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ind < E.size() && E[ind].X == i && E[ind].Y < 0) {
~~~~^~~~~~~~~~
walk.cpp:97:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ind2 < E.size() && E[ind2].X == i) {
~~~~~^~~~~~~~~~
walk.cpp:145:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ind < E.size() && E[ind].X == i && E[ind].Y > 0) {
~~~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
14456 KB |
Output is correct |
2 |
Correct |
13 ms |
14456 KB |
Output is correct |
3 |
Correct |
14 ms |
14456 KB |
Output is correct |
4 |
Correct |
16 ms |
14584 KB |
Output is correct |
5 |
Correct |
14 ms |
14584 KB |
Output is correct |
6 |
Correct |
15 ms |
14584 KB |
Output is correct |
7 |
Correct |
13 ms |
14584 KB |
Output is correct |
8 |
Correct |
14 ms |
14584 KB |
Output is correct |
9 |
Correct |
13 ms |
14456 KB |
Output is correct |
10 |
Correct |
14 ms |
14584 KB |
Output is correct |
11 |
Correct |
14 ms |
14456 KB |
Output is correct |
12 |
Correct |
14 ms |
14456 KB |
Output is correct |
13 |
Correct |
14 ms |
14584 KB |
Output is correct |
14 |
Correct |
14 ms |
14456 KB |
Output is correct |
15 |
Correct |
14 ms |
14460 KB |
Output is correct |
16 |
Correct |
14 ms |
14456 KB |
Output is correct |
17 |
Correct |
13 ms |
14456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
14456 KB |
Output is correct |
2 |
Correct |
13 ms |
14456 KB |
Output is correct |
3 |
Correct |
1087 ms |
70384 KB |
Output is correct |
4 |
Correct |
978 ms |
80792 KB |
Output is correct |
5 |
Correct |
677 ms |
66804 KB |
Output is correct |
6 |
Correct |
695 ms |
66556 KB |
Output is correct |
7 |
Correct |
698 ms |
67140 KB |
Output is correct |
8 |
Correct |
1105 ms |
72344 KB |
Output is correct |
9 |
Correct |
912 ms |
77076 KB |
Output is correct |
10 |
Correct |
1037 ms |
80924 KB |
Output is correct |
11 |
Correct |
910 ms |
69264 KB |
Output is correct |
12 |
Correct |
716 ms |
73492 KB |
Output is correct |
13 |
Correct |
988 ms |
82200 KB |
Output is correct |
14 |
Correct |
710 ms |
68388 KB |
Output is correct |
15 |
Correct |
715 ms |
70044 KB |
Output is correct |
16 |
Correct |
514 ms |
67480 KB |
Output is correct |
17 |
Correct |
504 ms |
65304 KB |
Output is correct |
18 |
Correct |
723 ms |
76436 KB |
Output is correct |
19 |
Correct |
36 ms |
17440 KB |
Output is correct |
20 |
Correct |
345 ms |
43024 KB |
Output is correct |
21 |
Correct |
458 ms |
64412 KB |
Output is correct |
22 |
Correct |
449 ms |
68756 KB |
Output is correct |
23 |
Correct |
754 ms |
76180 KB |
Output is correct |
24 |
Correct |
475 ms |
67992 KB |
Output is correct |
25 |
Correct |
455 ms |
64872 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
145 ms |
27388 KB |
Output is correct |
2 |
Correct |
1406 ms |
75544 KB |
Output is correct |
3 |
Correct |
1655 ms |
77216 KB |
Output is correct |
4 |
Correct |
1688 ms |
85324 KB |
Output is correct |
5 |
Correct |
2159 ms |
85276 KB |
Output is correct |
6 |
Correct |
1943 ms |
85400 KB |
Output is correct |
7 |
Correct |
630 ms |
55196 KB |
Output is correct |
8 |
Correct |
699 ms |
73496 KB |
Output is correct |
9 |
Correct |
1733 ms |
85400 KB |
Output is correct |
10 |
Correct |
625 ms |
69780 KB |
Output is correct |
11 |
Correct |
32 ms |
19448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
145 ms |
27388 KB |
Output is correct |
2 |
Correct |
1406 ms |
75544 KB |
Output is correct |
3 |
Correct |
1655 ms |
77216 KB |
Output is correct |
4 |
Correct |
1688 ms |
85324 KB |
Output is correct |
5 |
Correct |
2159 ms |
85276 KB |
Output is correct |
6 |
Correct |
1943 ms |
85400 KB |
Output is correct |
7 |
Correct |
630 ms |
55196 KB |
Output is correct |
8 |
Correct |
699 ms |
73496 KB |
Output is correct |
9 |
Correct |
1733 ms |
85400 KB |
Output is correct |
10 |
Correct |
625 ms |
69780 KB |
Output is correct |
11 |
Correct |
32 ms |
19448 KB |
Output is correct |
12 |
Correct |
1664 ms |
78880 KB |
Output is correct |
13 |
Correct |
1454 ms |
87352 KB |
Output is correct |
14 |
Correct |
2128 ms |
88980 KB |
Output is correct |
15 |
Correct |
1105 ms |
84632 KB |
Output is correct |
16 |
Correct |
1100 ms |
78976 KB |
Output is correct |
17 |
Correct |
1178 ms |
85784 KB |
Output is correct |
18 |
Correct |
1083 ms |
84632 KB |
Output is correct |
19 |
Correct |
909 ms |
78008 KB |
Output is correct |
20 |
Correct |
720 ms |
57172 KB |
Output is correct |
21 |
Correct |
63 ms |
25976 KB |
Output is correct |
22 |
Correct |
845 ms |
76416 KB |
Output is correct |
23 |
Correct |
802 ms |
76496 KB |
Output is correct |
24 |
Correct |
710 ms |
72336 KB |
Output is correct |
25 |
Correct |
746 ms |
74364 KB |
Output is correct |
26 |
Correct |
664 ms |
71712 KB |
Output is correct |
27 |
Correct |
2088 ms |
89112 KB |
Output is correct |
28 |
Correct |
1215 ms |
87160 KB |
Output is correct |
29 |
Correct |
2077 ms |
88984 KB |
Output is correct |
30 |
Correct |
650 ms |
57748 KB |
Output is correct |
31 |
Correct |
1755 ms |
88984 KB |
Output is correct |
32 |
Correct |
581 ms |
68380 KB |
Output is correct |
33 |
Correct |
573 ms |
70808 KB |
Output is correct |
34 |
Correct |
644 ms |
74060 KB |
Output is correct |
35 |
Correct |
670 ms |
74136 KB |
Output is correct |
36 |
Correct |
540 ms |
70344 KB |
Output is correct |
37 |
Correct |
458 ms |
66840 KB |
Output is correct |
38 |
Correct |
474 ms |
71576 KB |
Output is correct |
39 |
Correct |
770 ms |
78744 KB |
Output is correct |
40 |
Correct |
489 ms |
70552 KB |
Output is correct |
41 |
Correct |
452 ms |
67176 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
14456 KB |
Output is correct |
2 |
Correct |
13 ms |
14456 KB |
Output is correct |
3 |
Correct |
14 ms |
14456 KB |
Output is correct |
4 |
Correct |
16 ms |
14584 KB |
Output is correct |
5 |
Correct |
14 ms |
14584 KB |
Output is correct |
6 |
Correct |
15 ms |
14584 KB |
Output is correct |
7 |
Correct |
13 ms |
14584 KB |
Output is correct |
8 |
Correct |
14 ms |
14584 KB |
Output is correct |
9 |
Correct |
13 ms |
14456 KB |
Output is correct |
10 |
Correct |
14 ms |
14584 KB |
Output is correct |
11 |
Correct |
14 ms |
14456 KB |
Output is correct |
12 |
Correct |
14 ms |
14456 KB |
Output is correct |
13 |
Correct |
14 ms |
14584 KB |
Output is correct |
14 |
Correct |
14 ms |
14456 KB |
Output is correct |
15 |
Correct |
14 ms |
14460 KB |
Output is correct |
16 |
Correct |
14 ms |
14456 KB |
Output is correct |
17 |
Correct |
13 ms |
14456 KB |
Output is correct |
18 |
Correct |
14 ms |
14456 KB |
Output is correct |
19 |
Correct |
13 ms |
14456 KB |
Output is correct |
20 |
Correct |
1087 ms |
70384 KB |
Output is correct |
21 |
Correct |
978 ms |
80792 KB |
Output is correct |
22 |
Correct |
677 ms |
66804 KB |
Output is correct |
23 |
Correct |
695 ms |
66556 KB |
Output is correct |
24 |
Correct |
698 ms |
67140 KB |
Output is correct |
25 |
Correct |
1105 ms |
72344 KB |
Output is correct |
26 |
Correct |
912 ms |
77076 KB |
Output is correct |
27 |
Correct |
1037 ms |
80924 KB |
Output is correct |
28 |
Correct |
910 ms |
69264 KB |
Output is correct |
29 |
Correct |
716 ms |
73492 KB |
Output is correct |
30 |
Correct |
988 ms |
82200 KB |
Output is correct |
31 |
Correct |
710 ms |
68388 KB |
Output is correct |
32 |
Correct |
715 ms |
70044 KB |
Output is correct |
33 |
Correct |
514 ms |
67480 KB |
Output is correct |
34 |
Correct |
504 ms |
65304 KB |
Output is correct |
35 |
Correct |
723 ms |
76436 KB |
Output is correct |
36 |
Correct |
36 ms |
17440 KB |
Output is correct |
37 |
Correct |
345 ms |
43024 KB |
Output is correct |
38 |
Correct |
458 ms |
64412 KB |
Output is correct |
39 |
Correct |
449 ms |
68756 KB |
Output is correct |
40 |
Correct |
754 ms |
76180 KB |
Output is correct |
41 |
Correct |
475 ms |
67992 KB |
Output is correct |
42 |
Correct |
455 ms |
64872 KB |
Output is correct |
43 |
Correct |
145 ms |
27388 KB |
Output is correct |
44 |
Correct |
1406 ms |
75544 KB |
Output is correct |
45 |
Correct |
1655 ms |
77216 KB |
Output is correct |
46 |
Correct |
1688 ms |
85324 KB |
Output is correct |
47 |
Correct |
2159 ms |
85276 KB |
Output is correct |
48 |
Correct |
1943 ms |
85400 KB |
Output is correct |
49 |
Correct |
630 ms |
55196 KB |
Output is correct |
50 |
Correct |
699 ms |
73496 KB |
Output is correct |
51 |
Correct |
1733 ms |
85400 KB |
Output is correct |
52 |
Correct |
625 ms |
69780 KB |
Output is correct |
53 |
Correct |
32 ms |
19448 KB |
Output is correct |
54 |
Correct |
1664 ms |
78880 KB |
Output is correct |
55 |
Correct |
1454 ms |
87352 KB |
Output is correct |
56 |
Correct |
2128 ms |
88980 KB |
Output is correct |
57 |
Correct |
1105 ms |
84632 KB |
Output is correct |
58 |
Correct |
1100 ms |
78976 KB |
Output is correct |
59 |
Correct |
1178 ms |
85784 KB |
Output is correct |
60 |
Correct |
1083 ms |
84632 KB |
Output is correct |
61 |
Correct |
909 ms |
78008 KB |
Output is correct |
62 |
Correct |
720 ms |
57172 KB |
Output is correct |
63 |
Correct |
63 ms |
25976 KB |
Output is correct |
64 |
Correct |
845 ms |
76416 KB |
Output is correct |
65 |
Correct |
802 ms |
76496 KB |
Output is correct |
66 |
Correct |
710 ms |
72336 KB |
Output is correct |
67 |
Correct |
746 ms |
74364 KB |
Output is correct |
68 |
Correct |
664 ms |
71712 KB |
Output is correct |
69 |
Correct |
2088 ms |
89112 KB |
Output is correct |
70 |
Correct |
1215 ms |
87160 KB |
Output is correct |
71 |
Correct |
2077 ms |
88984 KB |
Output is correct |
72 |
Correct |
650 ms |
57748 KB |
Output is correct |
73 |
Correct |
1755 ms |
88984 KB |
Output is correct |
74 |
Correct |
581 ms |
68380 KB |
Output is correct |
75 |
Correct |
573 ms |
70808 KB |
Output is correct |
76 |
Correct |
644 ms |
74060 KB |
Output is correct |
77 |
Correct |
670 ms |
74136 KB |
Output is correct |
78 |
Correct |
540 ms |
70344 KB |
Output is correct |
79 |
Correct |
458 ms |
66840 KB |
Output is correct |
80 |
Correct |
474 ms |
71576 KB |
Output is correct |
81 |
Correct |
770 ms |
78744 KB |
Output is correct |
82 |
Correct |
489 ms |
70552 KB |
Output is correct |
83 |
Correct |
452 ms |
67176 KB |
Output is correct |
84 |
Correct |
124 ms |
25576 KB |
Output is correct |
85 |
Correct |
1695 ms |
81168 KB |
Output is correct |
86 |
Correct |
2475 ms |
104588 KB |
Output is correct |
87 |
Correct |
99 ms |
31216 KB |
Output is correct |
88 |
Correct |
103 ms |
30444 KB |
Output is correct |
89 |
Correct |
102 ms |
31216 KB |
Output is correct |
90 |
Correct |
48 ms |
18904 KB |
Output is correct |
91 |
Correct |
15 ms |
14712 KB |
Output is correct |
92 |
Correct |
46 ms |
17912 KB |
Output is correct |
93 |
Correct |
475 ms |
47404 KB |
Output is correct |
94 |
Correct |
66 ms |
26232 KB |
Output is correct |
95 |
Correct |
927 ms |
79084 KB |
Output is correct |
96 |
Correct |
787 ms |
76856 KB |
Output is correct |
97 |
Correct |
719 ms |
72332 KB |
Output is correct |
98 |
Correct |
739 ms |
74484 KB |
Output is correct |
99 |
Correct |
2968 ms |
124076 KB |
Output is correct |
100 |
Correct |
1381 ms |
89328 KB |
Output is correct |
101 |
Correct |
2095 ms |
100732 KB |
Output is correct |
102 |
Correct |
647 ms |
57984 KB |
Output is correct |
103 |
Correct |
561 ms |
68380 KB |
Output is correct |
104 |
Correct |
580 ms |
70748 KB |
Output is correct |
105 |
Correct |
679 ms |
73376 KB |
Output is correct |
106 |
Correct |
676 ms |
71992 KB |
Output is correct |
107 |
Correct |
714 ms |
74268 KB |
Output is correct |
108 |
Correct |
93 ms |
20588 KB |
Output is correct |
109 |
Correct |
1462 ms |
75096 KB |
Output is correct |
110 |
Correct |
1164 ms |
87596 KB |
Output is correct |
111 |
Correct |
1166 ms |
87944 KB |
Output is correct |
112 |
Correct |
644 ms |
72344 KB |
Output is correct |
113 |
Correct |
612 ms |
70900 KB |
Output is correct |