// ~ Be Name Khoda ~ //
#include "railroad.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn = 1e6 + 10;
const int maxn5 = 5e5 + 10;
const int maxnt = 1.2e6 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const ll inf = 1e18;
vector <int> num, adj[maxn5];
int cnt[maxn5], xx = 0, par[maxn5], cmp[maxn5];
bool mark[maxn5];
vector <pair<int, int>> ed;
void dfs(int v){
mark[v] = true;
cmp[v] = xx;
for(auto u : adj[v]) if(!mark[u])
dfs(u);
}
int get_par(int a){return par[a] == -1 ? a : par[a] = get_par(par[a]);}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
int n = s.size();
for(int i = 0; i < n; i++){
num.pb(s[i]);
num.pb(t[i]);
}
num.pb(0);
num.pb(mod);
sort(all(num));
num.resize(unique(all(num)) - num.begin());
for(int i = 0; i < n; i++) if(s[i] != t[i]){
s[i] = lower_bound(all(num), s[i]) - num.begin();
t[i] = lower_bound(all(num), t[i]) - num.begin();
adj[s[i]].pb(t[i]);
adj[t[i]].pb(s[i]);
cnt[t[i] + 1]--;
cnt[s[i] + 1]++;
}
adj[0].pb(int(num.size()) - 1);
adj[int(num.size()) - 1].pb(0);
cnt[1]--;
int cur = 0;
ll ans = 0;
for(int i = 0; i < num.size(); i++){
cur += cnt[i];
if(cur > 0)
ans += ll(cur) * (num[i] - num[i - 1]);
//cout << i << ' ' << cur << endl;
if(i && cur){
adj[i].pb(i - 1);
adj[i - 1].pb(i);
}
}
for(int i = 0; i < num.size(); i++) if(!mark[i]){
dfs(i);
xx++;
}
for(int i = 1; i < num.size(); i++) if(cmp[i] != cmp[i - 1])
ed.pb({num[i] - num[i - 1], i});
memset(par, -1, sizeof par);
sort(all(ed));
for(auto [val, id] : ed){
int u = get_par(cmp[id]), v = get_par(cmp[id - 1]);
if(u == v)
continue;
ans += val;
par[u] = v;
}
return ans;
}
Compilation message
railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:64:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for(int i = 0; i < num.size(); i++){
| ~~^~~~~~~~~~~~
railroad.cpp:74:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(int i = 0; i < num.size(); i++) if(!mark[i]){
| ~~^~~~~~~~~~~~
railroad.cpp:78:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int i = 1; i < num.size(); i++) if(cmp[i] != cmp[i - 1])
| ~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
13908 KB |
n = 2 |
2 |
Correct |
8 ms |
14036 KB |
n = 2 |
3 |
Correct |
7 ms |
13908 KB |
n = 2 |
4 |
Correct |
7 ms |
13908 KB |
n = 2 |
5 |
Correct |
8 ms |
13908 KB |
n = 2 |
6 |
Correct |
7 ms |
13968 KB |
n = 2 |
7 |
Correct |
7 ms |
13908 KB |
n = 3 |
8 |
Correct |
7 ms |
13964 KB |
n = 3 |
9 |
Correct |
7 ms |
13964 KB |
n = 3 |
10 |
Correct |
6 ms |
13968 KB |
n = 8 |
11 |
Correct |
7 ms |
14036 KB |
n = 8 |
12 |
Correct |
8 ms |
13908 KB |
n = 8 |
13 |
Correct |
7 ms |
13908 KB |
n = 8 |
14 |
Correct |
7 ms |
13908 KB |
n = 8 |
15 |
Correct |
7 ms |
13968 KB |
n = 8 |
16 |
Correct |
8 ms |
14036 KB |
n = 8 |
17 |
Correct |
7 ms |
13908 KB |
n = 8 |
18 |
Correct |
7 ms |
13908 KB |
n = 8 |
19 |
Correct |
7 ms |
13908 KB |
n = 3 |
20 |
Correct |
7 ms |
13908 KB |
n = 7 |
21 |
Correct |
7 ms |
13908 KB |
n = 8 |
22 |
Correct |
7 ms |
13908 KB |
n = 8 |
23 |
Correct |
7 ms |
13908 KB |
n = 8 |
24 |
Correct |
7 ms |
13968 KB |
n = 8 |
25 |
Correct |
7 ms |
13908 KB |
n = 8 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
13908 KB |
n = 2 |
2 |
Correct |
8 ms |
14036 KB |
n = 2 |
3 |
Correct |
7 ms |
13908 KB |
n = 2 |
4 |
Correct |
7 ms |
13908 KB |
n = 2 |
5 |
Correct |
8 ms |
13908 KB |
n = 2 |
6 |
Correct |
7 ms |
13968 KB |
n = 2 |
7 |
Correct |
7 ms |
13908 KB |
n = 3 |
8 |
Correct |
7 ms |
13964 KB |
n = 3 |
9 |
Correct |
7 ms |
13964 KB |
n = 3 |
10 |
Correct |
6 ms |
13968 KB |
n = 8 |
11 |
Correct |
7 ms |
14036 KB |
n = 8 |
12 |
Correct |
8 ms |
13908 KB |
n = 8 |
13 |
Correct |
7 ms |
13908 KB |
n = 8 |
14 |
Correct |
7 ms |
13908 KB |
n = 8 |
15 |
Correct |
7 ms |
13968 KB |
n = 8 |
16 |
Correct |
8 ms |
14036 KB |
n = 8 |
17 |
Correct |
7 ms |
13908 KB |
n = 8 |
18 |
Correct |
7 ms |
13908 KB |
n = 8 |
19 |
Correct |
7 ms |
13908 KB |
n = 3 |
20 |
Correct |
7 ms |
13908 KB |
n = 7 |
21 |
Correct |
7 ms |
13908 KB |
n = 8 |
22 |
Correct |
7 ms |
13908 KB |
n = 8 |
23 |
Correct |
7 ms |
13908 KB |
n = 8 |
24 |
Correct |
7 ms |
13968 KB |
n = 8 |
25 |
Correct |
7 ms |
13908 KB |
n = 8 |
26 |
Correct |
7 ms |
13968 KB |
n = 8 |
27 |
Correct |
7 ms |
13908 KB |
n = 8 |
28 |
Correct |
7 ms |
13908 KB |
n = 8 |
29 |
Correct |
7 ms |
13908 KB |
n = 16 |
30 |
Correct |
8 ms |
13964 KB |
n = 16 |
31 |
Correct |
7 ms |
13972 KB |
n = 16 |
32 |
Correct |
7 ms |
13964 KB |
n = 16 |
33 |
Correct |
8 ms |
13908 KB |
n = 16 |
34 |
Correct |
8 ms |
13936 KB |
n = 16 |
35 |
Correct |
8 ms |
13908 KB |
n = 16 |
36 |
Correct |
7 ms |
13908 KB |
n = 15 |
37 |
Correct |
7 ms |
13908 KB |
n = 8 |
38 |
Correct |
7 ms |
13964 KB |
n = 16 |
39 |
Correct |
7 ms |
13908 KB |
n = 16 |
40 |
Correct |
8 ms |
13908 KB |
n = 9 |
41 |
Correct |
7 ms |
13908 KB |
n = 16 |
42 |
Correct |
7 ms |
13964 KB |
n = 16 |
43 |
Correct |
7 ms |
13968 KB |
n = 16 |
44 |
Correct |
9 ms |
13968 KB |
n = 9 |
45 |
Correct |
7 ms |
13980 KB |
n = 15 |
46 |
Correct |
7 ms |
13908 KB |
n = 16 |
47 |
Correct |
7 ms |
13908 KB |
n = 16 |
48 |
Correct |
7 ms |
13968 KB |
n = 16 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
337 ms |
44368 KB |
n = 199999 |
2 |
Correct |
299 ms |
44388 KB |
n = 199991 |
3 |
Correct |
304 ms |
44400 KB |
n = 199993 |
4 |
Correct |
200 ms |
37112 KB |
n = 152076 |
5 |
Correct |
97 ms |
28196 KB |
n = 93249 |
6 |
Correct |
224 ms |
36816 KB |
n = 199910 |
7 |
Correct |
233 ms |
40564 KB |
n = 199999 |
8 |
Correct |
230 ms |
37304 KB |
n = 199997 |
9 |
Correct |
219 ms |
37888 KB |
n = 171294 |
10 |
Correct |
179 ms |
35500 KB |
n = 140872 |
11 |
Correct |
224 ms |
37240 KB |
n = 199886 |
12 |
Correct |
220 ms |
41224 KB |
n = 199996 |
13 |
Correct |
228 ms |
38508 KB |
n = 200000 |
14 |
Correct |
225 ms |
45004 KB |
n = 199998 |
15 |
Correct |
215 ms |
43504 KB |
n = 200000 |
16 |
Correct |
246 ms |
44216 KB |
n = 199998 |
17 |
Correct |
289 ms |
47528 KB |
n = 200000 |
18 |
Correct |
251 ms |
45852 KB |
n = 190000 |
19 |
Correct |
280 ms |
43732 KB |
n = 177777 |
20 |
Correct |
133 ms |
28192 KB |
n = 100000 |
21 |
Correct |
273 ms |
42420 KB |
n = 200000 |
22 |
Correct |
244 ms |
36712 KB |
n = 200000 |
23 |
Correct |
332 ms |
47484 KB |
n = 200000 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
13908 KB |
n = 2 |
2 |
Correct |
8 ms |
14036 KB |
n = 2 |
3 |
Correct |
7 ms |
13908 KB |
n = 2 |
4 |
Correct |
7 ms |
13908 KB |
n = 2 |
5 |
Correct |
8 ms |
13908 KB |
n = 2 |
6 |
Correct |
7 ms |
13968 KB |
n = 2 |
7 |
Correct |
7 ms |
13908 KB |
n = 3 |
8 |
Correct |
7 ms |
13964 KB |
n = 3 |
9 |
Correct |
7 ms |
13964 KB |
n = 3 |
10 |
Correct |
6 ms |
13968 KB |
n = 8 |
11 |
Correct |
7 ms |
14036 KB |
n = 8 |
12 |
Correct |
8 ms |
13908 KB |
n = 8 |
13 |
Correct |
7 ms |
13908 KB |
n = 8 |
14 |
Correct |
7 ms |
13908 KB |
n = 8 |
15 |
Correct |
7 ms |
13968 KB |
n = 8 |
16 |
Correct |
8 ms |
14036 KB |
n = 8 |
17 |
Correct |
7 ms |
13908 KB |
n = 8 |
18 |
Correct |
7 ms |
13908 KB |
n = 8 |
19 |
Correct |
7 ms |
13908 KB |
n = 3 |
20 |
Correct |
7 ms |
13908 KB |
n = 7 |
21 |
Correct |
7 ms |
13908 KB |
n = 8 |
22 |
Correct |
7 ms |
13908 KB |
n = 8 |
23 |
Correct |
7 ms |
13908 KB |
n = 8 |
24 |
Correct |
7 ms |
13968 KB |
n = 8 |
25 |
Correct |
7 ms |
13908 KB |
n = 8 |
26 |
Correct |
7 ms |
13968 KB |
n = 8 |
27 |
Correct |
7 ms |
13908 KB |
n = 8 |
28 |
Correct |
7 ms |
13908 KB |
n = 8 |
29 |
Correct |
7 ms |
13908 KB |
n = 16 |
30 |
Correct |
8 ms |
13964 KB |
n = 16 |
31 |
Correct |
7 ms |
13972 KB |
n = 16 |
32 |
Correct |
7 ms |
13964 KB |
n = 16 |
33 |
Correct |
8 ms |
13908 KB |
n = 16 |
34 |
Correct |
8 ms |
13936 KB |
n = 16 |
35 |
Correct |
8 ms |
13908 KB |
n = 16 |
36 |
Correct |
7 ms |
13908 KB |
n = 15 |
37 |
Correct |
7 ms |
13908 KB |
n = 8 |
38 |
Correct |
7 ms |
13964 KB |
n = 16 |
39 |
Correct |
7 ms |
13908 KB |
n = 16 |
40 |
Correct |
8 ms |
13908 KB |
n = 9 |
41 |
Correct |
7 ms |
13908 KB |
n = 16 |
42 |
Correct |
7 ms |
13964 KB |
n = 16 |
43 |
Correct |
7 ms |
13968 KB |
n = 16 |
44 |
Correct |
9 ms |
13968 KB |
n = 9 |
45 |
Correct |
7 ms |
13980 KB |
n = 15 |
46 |
Correct |
7 ms |
13908 KB |
n = 16 |
47 |
Correct |
7 ms |
13908 KB |
n = 16 |
48 |
Correct |
7 ms |
13968 KB |
n = 16 |
49 |
Correct |
337 ms |
44368 KB |
n = 199999 |
50 |
Correct |
299 ms |
44388 KB |
n = 199991 |
51 |
Correct |
304 ms |
44400 KB |
n = 199993 |
52 |
Correct |
200 ms |
37112 KB |
n = 152076 |
53 |
Correct |
97 ms |
28196 KB |
n = 93249 |
54 |
Correct |
224 ms |
36816 KB |
n = 199910 |
55 |
Correct |
233 ms |
40564 KB |
n = 199999 |
56 |
Correct |
230 ms |
37304 KB |
n = 199997 |
57 |
Correct |
219 ms |
37888 KB |
n = 171294 |
58 |
Correct |
179 ms |
35500 KB |
n = 140872 |
59 |
Correct |
224 ms |
37240 KB |
n = 199886 |
60 |
Correct |
220 ms |
41224 KB |
n = 199996 |
61 |
Correct |
228 ms |
38508 KB |
n = 200000 |
62 |
Correct |
225 ms |
45004 KB |
n = 199998 |
63 |
Correct |
215 ms |
43504 KB |
n = 200000 |
64 |
Correct |
246 ms |
44216 KB |
n = 199998 |
65 |
Correct |
289 ms |
47528 KB |
n = 200000 |
66 |
Correct |
251 ms |
45852 KB |
n = 190000 |
67 |
Correct |
280 ms |
43732 KB |
n = 177777 |
68 |
Correct |
133 ms |
28192 KB |
n = 100000 |
69 |
Correct |
273 ms |
42420 KB |
n = 200000 |
70 |
Correct |
244 ms |
36712 KB |
n = 200000 |
71 |
Correct |
332 ms |
47484 KB |
n = 200000 |
72 |
Correct |
325 ms |
48140 KB |
n = 200000 |
73 |
Correct |
307 ms |
48140 KB |
n = 200000 |
74 |
Correct |
297 ms |
48132 KB |
n = 200000 |
75 |
Correct |
297 ms |
51092 KB |
n = 200000 |
76 |
Correct |
306 ms |
51108 KB |
n = 200000 |
77 |
Correct |
89 ms |
35972 KB |
n = 200000 |
78 |
Correct |
93 ms |
25268 KB |
n = 200000 |
79 |
Correct |
298 ms |
41952 KB |
n = 184307 |
80 |
Correct |
99 ms |
26928 KB |
n = 76040 |
81 |
Correct |
234 ms |
39772 KB |
n = 199981 |
82 |
Correct |
232 ms |
44144 KB |
n = 199994 |
83 |
Correct |
242 ms |
41072 KB |
n = 199996 |
84 |
Correct |
238 ms |
47780 KB |
n = 199998 |
85 |
Correct |
265 ms |
46244 KB |
n = 200000 |
86 |
Correct |
231 ms |
47384 KB |
n = 199998 |
87 |
Correct |
240 ms |
51076 KB |
n = 200000 |
88 |
Correct |
276 ms |
51092 KB |
n = 200000 |
89 |
Correct |
263 ms |
51076 KB |
n = 200000 |
90 |
Correct |
282 ms |
45972 KB |
n = 200000 |
91 |
Correct |
290 ms |
40332 KB |
n = 200000 |
92 |
Correct |
295 ms |
51064 KB |
n = 200000 |