#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 400100;
vector <int> g[N];
bool used[N];
void dfs(int v){
used[v] = 1;
for (int i = 0; i < g[v].size(); i++){
int to = g[v][i];
if (!used[to])
dfs(to);
}
}
int dp[N], dsu[N], kol;
int dsu_get(int v){
if (v == dsu[v])
return v;
return dsu[v] = dsu_get(dsu[v]);
}
void dsu_unite(int a, int b){
a = dsu_get(a);
b = dsu_get(b);
if (a == b)
return;
dsu[b] = a;
--kol;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
vector <int> zhat;
s.push_back(1e9);
t.push_back(1);
for (int i = 0; i < s.size(); i++){
zhat.push_back(s[i]);
zhat.push_back(t[i]);
}
sort(zhat.begin(), zhat.end());
zhat.erase(unique(zhat.begin(), zhat.end()), zhat.end());
kol = zhat.size();
for (int i = 0; i < zhat.size(); i++)
dsu[i] = i;
memset(dp, 0, sizeof(dp));
for (int i = 0; i < s.size(); i++){
int ss = lower_bound(zhat.begin(), zhat.end(), s[i])-zhat.begin();
int tt = lower_bound(zhat.begin(), zhat.end(), t[i])-zhat.begin();
--dp[ss];
++dp[tt];
dsu_unite(ss, tt);
g[ss].push_back(tt);
}
int cur = 0;
ll ans = 0;
vector <pair<int, int> > edges;
for (int i = 0; i + 1 < zhat.size(); i++){
cur += dp[i];
if (cur > 0){
g[i].push_back(i+1);
dsu_unite(i, i+1);
}
if (cur < 0){
g[i+1].push_back(i);
ans -= cur*1ll*(zhat[i+1]-zhat[i]);
dsu_unite(i+1, i);
}
edges.push_back({zhat[i+1]-zhat[i], i});
}
sort(edges.begin(), edges.end());
for (int i = 0; i < edges.size(); i++){
int len = edges[i].first, id = edges[i].second;
int a = dsu_get(id), b = dsu_get(id+1);
if (a == b)
continue;
dsu_unite(a, b);
ans += len;
if (kol == 1)
break;
}
return ans;
}
Compilation message
railroad.cpp: In function 'void dfs(int)':
railroad.cpp:15:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[v].size(); i++){
~~^~~~~~~~~~~~~
railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:43:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < s.size(); i++){
~~^~~~~~~~~~
railroad.cpp:50:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < zhat.size(); i++)
~~^~~~~~~~~~~~~
railroad.cpp:53:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < s.size(); i++){
~~^~~~~~~~~~
railroad.cpp:64:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i + 1 < zhat.size(); i++){
~~~~~~^~~~~~~~~~~~~
railroad.cpp:78:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < edges.size(); i++){
~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
11256 KB |
n = 2 |
2 |
Correct |
11 ms |
11256 KB |
n = 2 |
3 |
Correct |
11 ms |
11256 KB |
n = 2 |
4 |
Correct |
11 ms |
11256 KB |
n = 2 |
5 |
Correct |
11 ms |
11256 KB |
n = 2 |
6 |
Correct |
11 ms |
11256 KB |
n = 2 |
7 |
Correct |
11 ms |
11256 KB |
n = 3 |
8 |
Correct |
11 ms |
11256 KB |
n = 3 |
9 |
Correct |
11 ms |
11336 KB |
n = 3 |
10 |
Correct |
11 ms |
11276 KB |
n = 8 |
11 |
Correct |
11 ms |
11256 KB |
n = 8 |
12 |
Correct |
11 ms |
11256 KB |
n = 8 |
13 |
Correct |
11 ms |
11256 KB |
n = 8 |
14 |
Correct |
11 ms |
11256 KB |
n = 8 |
15 |
Correct |
11 ms |
11256 KB |
n = 8 |
16 |
Correct |
11 ms |
11256 KB |
n = 8 |
17 |
Correct |
11 ms |
11256 KB |
n = 8 |
18 |
Correct |
11 ms |
11272 KB |
n = 8 |
19 |
Correct |
11 ms |
11256 KB |
n = 3 |
20 |
Correct |
11 ms |
11256 KB |
n = 7 |
21 |
Correct |
11 ms |
11256 KB |
n = 8 |
22 |
Correct |
11 ms |
11256 KB |
n = 8 |
23 |
Correct |
12 ms |
11256 KB |
n = 8 |
24 |
Correct |
11 ms |
11256 KB |
n = 8 |
25 |
Correct |
11 ms |
11256 KB |
n = 8 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
11256 KB |
n = 2 |
2 |
Correct |
11 ms |
11256 KB |
n = 2 |
3 |
Correct |
11 ms |
11256 KB |
n = 2 |
4 |
Correct |
11 ms |
11256 KB |
n = 2 |
5 |
Correct |
11 ms |
11256 KB |
n = 2 |
6 |
Correct |
11 ms |
11256 KB |
n = 2 |
7 |
Correct |
11 ms |
11256 KB |
n = 3 |
8 |
Correct |
11 ms |
11256 KB |
n = 3 |
9 |
Correct |
11 ms |
11336 KB |
n = 3 |
10 |
Correct |
11 ms |
11276 KB |
n = 8 |
11 |
Correct |
11 ms |
11256 KB |
n = 8 |
12 |
Correct |
11 ms |
11256 KB |
n = 8 |
13 |
Correct |
11 ms |
11256 KB |
n = 8 |
14 |
Correct |
11 ms |
11256 KB |
n = 8 |
15 |
Correct |
11 ms |
11256 KB |
n = 8 |
16 |
Correct |
11 ms |
11256 KB |
n = 8 |
17 |
Correct |
11 ms |
11256 KB |
n = 8 |
18 |
Correct |
11 ms |
11272 KB |
n = 8 |
19 |
Correct |
11 ms |
11256 KB |
n = 3 |
20 |
Correct |
11 ms |
11256 KB |
n = 7 |
21 |
Correct |
11 ms |
11256 KB |
n = 8 |
22 |
Correct |
11 ms |
11256 KB |
n = 8 |
23 |
Correct |
12 ms |
11256 KB |
n = 8 |
24 |
Correct |
11 ms |
11256 KB |
n = 8 |
25 |
Correct |
11 ms |
11256 KB |
n = 8 |
26 |
Correct |
11 ms |
11256 KB |
n = 8 |
27 |
Correct |
11 ms |
11256 KB |
n = 8 |
28 |
Correct |
11 ms |
11256 KB |
n = 8 |
29 |
Correct |
11 ms |
11256 KB |
n = 16 |
30 |
Correct |
11 ms |
11256 KB |
n = 16 |
31 |
Correct |
11 ms |
11280 KB |
n = 16 |
32 |
Correct |
11 ms |
11256 KB |
n = 16 |
33 |
Correct |
14 ms |
11260 KB |
n = 16 |
34 |
Correct |
13 ms |
11260 KB |
n = 16 |
35 |
Correct |
12 ms |
11220 KB |
n = 16 |
36 |
Correct |
11 ms |
11256 KB |
n = 15 |
37 |
Correct |
11 ms |
11256 KB |
n = 8 |
38 |
Correct |
11 ms |
11300 KB |
n = 16 |
39 |
Correct |
12 ms |
11256 KB |
n = 16 |
40 |
Correct |
11 ms |
11256 KB |
n = 9 |
41 |
Correct |
11 ms |
11228 KB |
n = 16 |
42 |
Correct |
11 ms |
11256 KB |
n = 16 |
43 |
Correct |
11 ms |
11256 KB |
n = 16 |
44 |
Correct |
11 ms |
11256 KB |
n = 9 |
45 |
Correct |
11 ms |
11256 KB |
n = 15 |
46 |
Correct |
11 ms |
11256 KB |
n = 16 |
47 |
Correct |
12 ms |
11256 KB |
n = 16 |
48 |
Correct |
12 ms |
11256 KB |
n = 16 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
372 ms |
34608 KB |
n = 199999 |
2 |
Correct |
426 ms |
34112 KB |
n = 199991 |
3 |
Correct |
411 ms |
34276 KB |
n = 199993 |
4 |
Correct |
301 ms |
30156 KB |
n = 152076 |
5 |
Correct |
158 ms |
22164 KB |
n = 93249 |
6 |
Correct |
319 ms |
31444 KB |
n = 199910 |
7 |
Correct |
358 ms |
33528 KB |
n = 199999 |
8 |
Correct |
326 ms |
31448 KB |
n = 199997 |
9 |
Correct |
324 ms |
31028 KB |
n = 171294 |
10 |
Correct |
254 ms |
29092 KB |
n = 140872 |
11 |
Correct |
320 ms |
31428 KB |
n = 199886 |
12 |
Correct |
357 ms |
33616 KB |
n = 199996 |
13 |
Correct |
321 ms |
31780 KB |
n = 200000 |
14 |
Correct |
343 ms |
33744 KB |
n = 199998 |
15 |
Correct |
347 ms |
33316 KB |
n = 200000 |
16 |
Correct |
361 ms |
34000 KB |
n = 199998 |
17 |
Correct |
363 ms |
37256 KB |
n = 200000 |
18 |
Correct |
353 ms |
33072 KB |
n = 190000 |
19 |
Correct |
316 ms |
32776 KB |
n = 177777 |
20 |
Correct |
177 ms |
22880 KB |
n = 100000 |
21 |
Correct |
382 ms |
34128 KB |
n = 200000 |
22 |
Correct |
401 ms |
34208 KB |
n = 200000 |
23 |
Correct |
357 ms |
34172 KB |
n = 200000 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
11256 KB |
n = 2 |
2 |
Correct |
11 ms |
11256 KB |
n = 2 |
3 |
Correct |
11 ms |
11256 KB |
n = 2 |
4 |
Correct |
11 ms |
11256 KB |
n = 2 |
5 |
Correct |
11 ms |
11256 KB |
n = 2 |
6 |
Correct |
11 ms |
11256 KB |
n = 2 |
7 |
Correct |
11 ms |
11256 KB |
n = 3 |
8 |
Correct |
11 ms |
11256 KB |
n = 3 |
9 |
Correct |
11 ms |
11336 KB |
n = 3 |
10 |
Correct |
11 ms |
11276 KB |
n = 8 |
11 |
Correct |
11 ms |
11256 KB |
n = 8 |
12 |
Correct |
11 ms |
11256 KB |
n = 8 |
13 |
Correct |
11 ms |
11256 KB |
n = 8 |
14 |
Correct |
11 ms |
11256 KB |
n = 8 |
15 |
Correct |
11 ms |
11256 KB |
n = 8 |
16 |
Correct |
11 ms |
11256 KB |
n = 8 |
17 |
Correct |
11 ms |
11256 KB |
n = 8 |
18 |
Correct |
11 ms |
11272 KB |
n = 8 |
19 |
Correct |
11 ms |
11256 KB |
n = 3 |
20 |
Correct |
11 ms |
11256 KB |
n = 7 |
21 |
Correct |
11 ms |
11256 KB |
n = 8 |
22 |
Correct |
11 ms |
11256 KB |
n = 8 |
23 |
Correct |
12 ms |
11256 KB |
n = 8 |
24 |
Correct |
11 ms |
11256 KB |
n = 8 |
25 |
Correct |
11 ms |
11256 KB |
n = 8 |
26 |
Correct |
11 ms |
11256 KB |
n = 8 |
27 |
Correct |
11 ms |
11256 KB |
n = 8 |
28 |
Correct |
11 ms |
11256 KB |
n = 8 |
29 |
Correct |
11 ms |
11256 KB |
n = 16 |
30 |
Correct |
11 ms |
11256 KB |
n = 16 |
31 |
Correct |
11 ms |
11280 KB |
n = 16 |
32 |
Correct |
11 ms |
11256 KB |
n = 16 |
33 |
Correct |
14 ms |
11260 KB |
n = 16 |
34 |
Correct |
13 ms |
11260 KB |
n = 16 |
35 |
Correct |
12 ms |
11220 KB |
n = 16 |
36 |
Correct |
11 ms |
11256 KB |
n = 15 |
37 |
Correct |
11 ms |
11256 KB |
n = 8 |
38 |
Correct |
11 ms |
11300 KB |
n = 16 |
39 |
Correct |
12 ms |
11256 KB |
n = 16 |
40 |
Correct |
11 ms |
11256 KB |
n = 9 |
41 |
Correct |
11 ms |
11228 KB |
n = 16 |
42 |
Correct |
11 ms |
11256 KB |
n = 16 |
43 |
Correct |
11 ms |
11256 KB |
n = 16 |
44 |
Correct |
11 ms |
11256 KB |
n = 9 |
45 |
Correct |
11 ms |
11256 KB |
n = 15 |
46 |
Correct |
11 ms |
11256 KB |
n = 16 |
47 |
Correct |
12 ms |
11256 KB |
n = 16 |
48 |
Correct |
12 ms |
11256 KB |
n = 16 |
49 |
Correct |
372 ms |
34608 KB |
n = 199999 |
50 |
Correct |
426 ms |
34112 KB |
n = 199991 |
51 |
Correct |
411 ms |
34276 KB |
n = 199993 |
52 |
Correct |
301 ms |
30156 KB |
n = 152076 |
53 |
Correct |
158 ms |
22164 KB |
n = 93249 |
54 |
Correct |
319 ms |
31444 KB |
n = 199910 |
55 |
Correct |
358 ms |
33528 KB |
n = 199999 |
56 |
Correct |
326 ms |
31448 KB |
n = 199997 |
57 |
Correct |
324 ms |
31028 KB |
n = 171294 |
58 |
Correct |
254 ms |
29092 KB |
n = 140872 |
59 |
Correct |
320 ms |
31428 KB |
n = 199886 |
60 |
Correct |
357 ms |
33616 KB |
n = 199996 |
61 |
Correct |
321 ms |
31780 KB |
n = 200000 |
62 |
Correct |
343 ms |
33744 KB |
n = 199998 |
63 |
Correct |
347 ms |
33316 KB |
n = 200000 |
64 |
Correct |
361 ms |
34000 KB |
n = 199998 |
65 |
Correct |
363 ms |
37256 KB |
n = 200000 |
66 |
Correct |
353 ms |
33072 KB |
n = 190000 |
67 |
Correct |
316 ms |
32776 KB |
n = 177777 |
68 |
Correct |
177 ms |
22880 KB |
n = 100000 |
69 |
Correct |
382 ms |
34128 KB |
n = 200000 |
70 |
Correct |
401 ms |
34208 KB |
n = 200000 |
71 |
Correct |
357 ms |
34172 KB |
n = 200000 |
72 |
Correct |
366 ms |
34068 KB |
n = 200000 |
73 |
Correct |
406 ms |
33800 KB |
n = 200000 |
74 |
Correct |
421 ms |
33992 KB |
n = 200000 |
75 |
Correct |
348 ms |
37196 KB |
n = 200000 |
76 |
Correct |
350 ms |
38272 KB |
n = 200000 |
77 |
Correct |
277 ms |
30036 KB |
n = 200000 |
78 |
Correct |
263 ms |
30064 KB |
n = 200000 |
79 |
Correct |
341 ms |
34896 KB |
n = 184307 |
80 |
Correct |
148 ms |
21816 KB |
n = 76040 |
81 |
Correct |
324 ms |
33720 KB |
n = 199981 |
82 |
Correct |
350 ms |
36416 KB |
n = 199994 |
83 |
Correct |
329 ms |
34052 KB |
n = 199996 |
84 |
Correct |
338 ms |
36280 KB |
n = 199998 |
85 |
Correct |
340 ms |
35824 KB |
n = 200000 |
86 |
Correct |
354 ms |
36752 KB |
n = 199998 |
87 |
Correct |
352 ms |
40268 KB |
n = 200000 |
88 |
Correct |
428 ms |
37876 KB |
n = 200000 |
89 |
Correct |
342 ms |
38200 KB |
n = 200000 |
90 |
Correct |
380 ms |
37148 KB |
n = 200000 |
91 |
Correct |
354 ms |
37080 KB |
n = 200000 |
92 |
Correct |
354 ms |
37124 KB |
n = 200000 |