#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define eb emplace_back
#define x first
#define y second
using pp=pair<int,int>;
using ll=long long;
map<int,int> df;
const int inf = int(1e9) + 10;
const int maxn = int(4e5) + 10;
int par[maxn];
vector<pp> D;
int R(int x){ return (par[x]==x) ? x : (par[x]=R(par[x])); }
vector<tuple<int,int,int>> ev;
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
int n = s.size();
for(int i=0; i<n; ++i) {
df[s[i]] += -1;
df[t[i]] += +1;
}
df[0] += +1;
df[inf] += -1;
D = vector<pp>(df.begin(), df.end());
int sz = D.size();
iota(par, par+sz, 0);
ll ans = 0;
int lev = 0, last = 0;
for(int i=0; i<sz; ++i) {
auto &tmp = D[i];
if(lev < 0) {
ans += (tmp.x - last) * 1ll * (-lev);
}
if(lev && i) {
par[R(i-1)] = i;
}
last = tmp.x;
lev += tmp.y;
}
auto fnd = [&](int x){ return int(lower_bound(D.begin(), D.end(), pp(x, -inf)) - D.begin()); };
for(int i=0; i<n; ++i) {
par[R(fnd(s[i]))] = R(fnd(t[i]));
}
par[R(fnd(0))] = R(fnd(inf));
for(int i=0; i+1<sz; ++i) {
int va = R(i), vb = R(i+1);
if(va != vb) ev.eb(D[i+1].x-D[i].x, va, vb);
}
sort(ev.begin(), ev.end());
for(auto &tmp:ev) {
int v, a, b; tie(v, a, b) = tmp;
if(R(a) != R(b)) {
ans += v;
par[R(a)] = R(b);
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
380 KB |
n = 2 |
2 |
Correct |
2 ms |
256 KB |
n = 2 |
3 |
Correct |
2 ms |
376 KB |
n = 2 |
4 |
Correct |
2 ms |
376 KB |
n = 2 |
5 |
Correct |
1 ms |
376 KB |
n = 2 |
6 |
Correct |
2 ms |
256 KB |
n = 2 |
7 |
Correct |
1 ms |
376 KB |
n = 3 |
8 |
Correct |
2 ms |
376 KB |
n = 3 |
9 |
Correct |
2 ms |
376 KB |
n = 3 |
10 |
Correct |
2 ms |
256 KB |
n = 8 |
11 |
Correct |
2 ms |
256 KB |
n = 8 |
12 |
Correct |
2 ms |
256 KB |
n = 8 |
13 |
Correct |
2 ms |
376 KB |
n = 8 |
14 |
Correct |
2 ms |
376 KB |
n = 8 |
15 |
Correct |
2 ms |
256 KB |
n = 8 |
16 |
Correct |
2 ms |
376 KB |
n = 8 |
17 |
Correct |
2 ms |
376 KB |
n = 8 |
18 |
Correct |
2 ms |
376 KB |
n = 8 |
19 |
Correct |
2 ms |
256 KB |
n = 3 |
20 |
Correct |
2 ms |
376 KB |
n = 7 |
21 |
Correct |
2 ms |
256 KB |
n = 8 |
22 |
Correct |
2 ms |
256 KB |
n = 8 |
23 |
Correct |
2 ms |
256 KB |
n = 8 |
24 |
Correct |
2 ms |
256 KB |
n = 8 |
25 |
Correct |
2 ms |
256 KB |
n = 8 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
380 KB |
n = 2 |
2 |
Correct |
2 ms |
256 KB |
n = 2 |
3 |
Correct |
2 ms |
376 KB |
n = 2 |
4 |
Correct |
2 ms |
376 KB |
n = 2 |
5 |
Correct |
1 ms |
376 KB |
n = 2 |
6 |
Correct |
2 ms |
256 KB |
n = 2 |
7 |
Correct |
1 ms |
376 KB |
n = 3 |
8 |
Correct |
2 ms |
376 KB |
n = 3 |
9 |
Correct |
2 ms |
376 KB |
n = 3 |
10 |
Correct |
2 ms |
256 KB |
n = 8 |
11 |
Correct |
2 ms |
256 KB |
n = 8 |
12 |
Correct |
2 ms |
256 KB |
n = 8 |
13 |
Correct |
2 ms |
376 KB |
n = 8 |
14 |
Correct |
2 ms |
376 KB |
n = 8 |
15 |
Correct |
2 ms |
256 KB |
n = 8 |
16 |
Correct |
2 ms |
376 KB |
n = 8 |
17 |
Correct |
2 ms |
376 KB |
n = 8 |
18 |
Correct |
2 ms |
376 KB |
n = 8 |
19 |
Correct |
2 ms |
256 KB |
n = 3 |
20 |
Correct |
2 ms |
376 KB |
n = 7 |
21 |
Correct |
2 ms |
256 KB |
n = 8 |
22 |
Correct |
2 ms |
256 KB |
n = 8 |
23 |
Correct |
2 ms |
256 KB |
n = 8 |
24 |
Correct |
2 ms |
256 KB |
n = 8 |
25 |
Correct |
2 ms |
256 KB |
n = 8 |
26 |
Correct |
2 ms |
376 KB |
n = 8 |
27 |
Correct |
2 ms |
376 KB |
n = 8 |
28 |
Correct |
2 ms |
376 KB |
n = 8 |
29 |
Correct |
2 ms |
376 KB |
n = 16 |
30 |
Correct |
2 ms |
376 KB |
n = 16 |
31 |
Correct |
2 ms |
256 KB |
n = 16 |
32 |
Correct |
2 ms |
504 KB |
n = 16 |
33 |
Correct |
2 ms |
256 KB |
n = 16 |
34 |
Correct |
2 ms |
256 KB |
n = 16 |
35 |
Correct |
2 ms |
376 KB |
n = 16 |
36 |
Correct |
2 ms |
376 KB |
n = 15 |
37 |
Correct |
2 ms |
256 KB |
n = 8 |
38 |
Correct |
2 ms |
256 KB |
n = 16 |
39 |
Correct |
2 ms |
376 KB |
n = 16 |
40 |
Correct |
2 ms |
380 KB |
n = 9 |
41 |
Correct |
2 ms |
256 KB |
n = 16 |
42 |
Correct |
2 ms |
256 KB |
n = 16 |
43 |
Correct |
2 ms |
376 KB |
n = 16 |
44 |
Correct |
2 ms |
376 KB |
n = 9 |
45 |
Correct |
2 ms |
376 KB |
n = 15 |
46 |
Correct |
2 ms |
376 KB |
n = 16 |
47 |
Correct |
2 ms |
376 KB |
n = 16 |
48 |
Correct |
3 ms |
376 KB |
n = 16 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
604 ms |
33656 KB |
n = 199999 |
2 |
Correct |
699 ms |
35588 KB |
n = 199991 |
3 |
Correct |
692 ms |
34140 KB |
n = 199993 |
4 |
Correct |
530 ms |
26756 KB |
n = 152076 |
5 |
Correct |
254 ms |
17400 KB |
n = 93249 |
6 |
Correct |
513 ms |
28156 KB |
n = 199910 |
7 |
Correct |
527 ms |
32988 KB |
n = 199999 |
8 |
Correct |
466 ms |
28340 KB |
n = 199997 |
9 |
Correct |
531 ms |
29028 KB |
n = 171294 |
10 |
Correct |
427 ms |
24720 KB |
n = 140872 |
11 |
Correct |
573 ms |
25844 KB |
n = 199886 |
12 |
Correct |
527 ms |
29928 KB |
n = 199996 |
13 |
Correct |
468 ms |
26616 KB |
n = 200000 |
14 |
Correct |
492 ms |
30368 KB |
n = 199998 |
15 |
Correct |
509 ms |
30016 KB |
n = 200000 |
16 |
Correct |
505 ms |
31192 KB |
n = 199998 |
17 |
Correct |
554 ms |
33920 KB |
n = 200000 |
18 |
Correct |
534 ms |
29916 KB |
n = 190000 |
19 |
Correct |
476 ms |
30456 KB |
n = 177777 |
20 |
Correct |
229 ms |
15864 KB |
n = 100000 |
21 |
Correct |
536 ms |
31136 KB |
n = 200000 |
22 |
Correct |
580 ms |
34156 KB |
n = 200000 |
23 |
Correct |
613 ms |
30968 KB |
n = 200000 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
380 KB |
n = 2 |
2 |
Correct |
2 ms |
256 KB |
n = 2 |
3 |
Correct |
2 ms |
376 KB |
n = 2 |
4 |
Correct |
2 ms |
376 KB |
n = 2 |
5 |
Correct |
1 ms |
376 KB |
n = 2 |
6 |
Correct |
2 ms |
256 KB |
n = 2 |
7 |
Correct |
1 ms |
376 KB |
n = 3 |
8 |
Correct |
2 ms |
376 KB |
n = 3 |
9 |
Correct |
2 ms |
376 KB |
n = 3 |
10 |
Correct |
2 ms |
256 KB |
n = 8 |
11 |
Correct |
2 ms |
256 KB |
n = 8 |
12 |
Correct |
2 ms |
256 KB |
n = 8 |
13 |
Correct |
2 ms |
376 KB |
n = 8 |
14 |
Correct |
2 ms |
376 KB |
n = 8 |
15 |
Correct |
2 ms |
256 KB |
n = 8 |
16 |
Correct |
2 ms |
376 KB |
n = 8 |
17 |
Correct |
2 ms |
376 KB |
n = 8 |
18 |
Correct |
2 ms |
376 KB |
n = 8 |
19 |
Correct |
2 ms |
256 KB |
n = 3 |
20 |
Correct |
2 ms |
376 KB |
n = 7 |
21 |
Correct |
2 ms |
256 KB |
n = 8 |
22 |
Correct |
2 ms |
256 KB |
n = 8 |
23 |
Correct |
2 ms |
256 KB |
n = 8 |
24 |
Correct |
2 ms |
256 KB |
n = 8 |
25 |
Correct |
2 ms |
256 KB |
n = 8 |
26 |
Correct |
2 ms |
376 KB |
n = 8 |
27 |
Correct |
2 ms |
376 KB |
n = 8 |
28 |
Correct |
2 ms |
376 KB |
n = 8 |
29 |
Correct |
2 ms |
376 KB |
n = 16 |
30 |
Correct |
2 ms |
376 KB |
n = 16 |
31 |
Correct |
2 ms |
256 KB |
n = 16 |
32 |
Correct |
2 ms |
504 KB |
n = 16 |
33 |
Correct |
2 ms |
256 KB |
n = 16 |
34 |
Correct |
2 ms |
256 KB |
n = 16 |
35 |
Correct |
2 ms |
376 KB |
n = 16 |
36 |
Correct |
2 ms |
376 KB |
n = 15 |
37 |
Correct |
2 ms |
256 KB |
n = 8 |
38 |
Correct |
2 ms |
256 KB |
n = 16 |
39 |
Correct |
2 ms |
376 KB |
n = 16 |
40 |
Correct |
2 ms |
380 KB |
n = 9 |
41 |
Correct |
2 ms |
256 KB |
n = 16 |
42 |
Correct |
2 ms |
256 KB |
n = 16 |
43 |
Correct |
2 ms |
376 KB |
n = 16 |
44 |
Correct |
2 ms |
376 KB |
n = 9 |
45 |
Correct |
2 ms |
376 KB |
n = 15 |
46 |
Correct |
2 ms |
376 KB |
n = 16 |
47 |
Correct |
2 ms |
376 KB |
n = 16 |
48 |
Correct |
3 ms |
376 KB |
n = 16 |
49 |
Correct |
604 ms |
33656 KB |
n = 199999 |
50 |
Correct |
699 ms |
35588 KB |
n = 199991 |
51 |
Correct |
692 ms |
34140 KB |
n = 199993 |
52 |
Correct |
530 ms |
26756 KB |
n = 152076 |
53 |
Correct |
254 ms |
17400 KB |
n = 93249 |
54 |
Correct |
513 ms |
28156 KB |
n = 199910 |
55 |
Correct |
527 ms |
32988 KB |
n = 199999 |
56 |
Correct |
466 ms |
28340 KB |
n = 199997 |
57 |
Correct |
531 ms |
29028 KB |
n = 171294 |
58 |
Correct |
427 ms |
24720 KB |
n = 140872 |
59 |
Correct |
573 ms |
25844 KB |
n = 199886 |
60 |
Correct |
527 ms |
29928 KB |
n = 199996 |
61 |
Correct |
468 ms |
26616 KB |
n = 200000 |
62 |
Correct |
492 ms |
30368 KB |
n = 199998 |
63 |
Correct |
509 ms |
30016 KB |
n = 200000 |
64 |
Correct |
505 ms |
31192 KB |
n = 199998 |
65 |
Correct |
554 ms |
33920 KB |
n = 200000 |
66 |
Correct |
534 ms |
29916 KB |
n = 190000 |
67 |
Correct |
476 ms |
30456 KB |
n = 177777 |
68 |
Correct |
229 ms |
15864 KB |
n = 100000 |
69 |
Correct |
536 ms |
31136 KB |
n = 200000 |
70 |
Correct |
580 ms |
34156 KB |
n = 200000 |
71 |
Correct |
613 ms |
30968 KB |
n = 200000 |
72 |
Correct |
644 ms |
34384 KB |
n = 200000 |
73 |
Correct |
621 ms |
34192 KB |
n = 200000 |
74 |
Correct |
621 ms |
36400 KB |
n = 200000 |
75 |
Correct |
551 ms |
33616 KB |
n = 200000 |
76 |
Correct |
628 ms |
34608 KB |
n = 200000 |
77 |
Correct |
337 ms |
21608 KB |
n = 200000 |
78 |
Correct |
391 ms |
22500 KB |
n = 200000 |
79 |
Correct |
572 ms |
30748 KB |
n = 184307 |
80 |
Correct |
181 ms |
14328 KB |
n = 76040 |
81 |
Correct |
519 ms |
25968 KB |
n = 199981 |
82 |
Correct |
539 ms |
29888 KB |
n = 199994 |
83 |
Correct |
465 ms |
26744 KB |
n = 199996 |
84 |
Correct |
504 ms |
30484 KB |
n = 199998 |
85 |
Correct |
491 ms |
30084 KB |
n = 200000 |
86 |
Correct |
498 ms |
31192 KB |
n = 199998 |
87 |
Correct |
566 ms |
34112 KB |
n = 200000 |
88 |
Correct |
572 ms |
31624 KB |
n = 200000 |
89 |
Correct |
549 ms |
34512 KB |
n = 200000 |
90 |
Correct |
556 ms |
31064 KB |
n = 200000 |
91 |
Correct |
615 ms |
34088 KB |
n = 200000 |
92 |
Correct |
641 ms |
30840 KB |
n = 200000 |