#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using Edge = pair<ll, pll>;
#define fi first
#define se second
const ll maxN = 17;
const ll INF = 1e18;
ll n;
vector<ll> compress;
vector<ll> cs, ct;
struct DSU {
vector<ll> par, sz;
DSU(ll n) {
par = sz = vector<ll>(n+1, 1);
iota(par.begin(), par.end(), 0);
}
ll rep(ll x) {
return ((x == par[x]) ? (x) : (par[x] = rep(par[x])));
}
bool check(ll x, ll y) {
return (rep(x) == rep(y));
}
void join(ll x, ll y) {
ll a = rep(x), b = rep(y);
if (a == b) return;
if (sz[a] < sz[b]) {swap(a, b);}
par[b] = a;
sz[a] += sz[b];
}
};
ll plan_roller_coaster(vector<int> s, vector<int> t) {
n = s.size();
for (auto i : s) {compress.push_back(i);}
for (auto i : t) {compress.push_back(i);}
compress.push_back(0);
compress.push_back(INF);
sort(compress.begin(), compress.end());
compress.erase(unique(compress.begin(), compress.end()), compress.end());
for (auto i : s) {
cs.push_back(lower_bound(compress.begin(), compress.end(), i) - compress.begin());
}
for (auto i : t) {
ct.push_back(lower_bound(compress.begin(), compress.end(), i) - compress.begin());
}
ll CS = compress.size();
DSU D = DSU(CS);
//for (auto i : compress) cout << i << ' '; cout << '\n';
// edges for MST
vector<Edge> edges;
for (ll i = 1; i < compress.size(); i++) {
edges.push_back({compress[i] - compress[i-1], {i-1, i}});
}
vector<ll> lines(CS, 0);
// right line = 1, left line = -1
for (ll i = 0; i < n; i++) {
D.join(cs[i], ct[i]);
//cout << i << ' ' << cs[i] << ' ' << ct[i] << '\n';
if (s[i] < t[i]) {
// right line
lines[cs[i]]++;
lines[ct[i]]--;
} else {
// left line
lines[ct[i]]--;
lines[cs[i]]++;
}
}
lines[0]--;
//for (auto i : lines) cout << i << ' '; cout << '\n';
ll run = 0, ans = 0;
for (ll i = 0; i < CS-1; i++) {
run += lines[i];
//cout << run << ' ';
if (run > 0) {
// more right lines than left lines
ans += 1ll * run * (compress[i+1] - compress[i]);
D.join(i, i+1);
} else if (run < 0) {
// more left lines than right lines
D.join(i, i+1);
}
}
//cout << '\n';
// make the graph connected via Kruskal
sort(edges.begin(), edges.end());
for (auto &[w, p] : edges) {
if (D.check(p.fi, p.se)) continue;
ans += compress[p.se] - compress[p.fi];
D.join(p.fi, p.se);
}
return ans;
}
#ifdef Zanite
int main() {
int n;
assert(1 == scanf("%d", &n));
std::vector<int> s(n), t(n);
for (int i = 0; i < n; ++i)
assert(2 == scanf("%d%d", &s[i], &t[i]));
long long ans = plan_roller_coaster(s, t);
printf("%lld\n", ans);
return 0;
}
#endif
Compilation message
railroad.cpp: In function 'll plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:69:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for (ll i = 1; i < compress.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
n = 2 |
2 |
Correct |
1 ms |
212 KB |
n = 2 |
3 |
Correct |
0 ms |
212 KB |
n = 2 |
4 |
Correct |
0 ms |
212 KB |
n = 2 |
5 |
Correct |
0 ms |
212 KB |
n = 2 |
6 |
Correct |
0 ms |
212 KB |
n = 2 |
7 |
Correct |
0 ms |
212 KB |
n = 3 |
8 |
Correct |
0 ms |
212 KB |
n = 3 |
9 |
Correct |
0 ms |
212 KB |
n = 3 |
10 |
Correct |
1 ms |
212 KB |
n = 8 |
11 |
Correct |
0 ms |
212 KB |
n = 8 |
12 |
Correct |
0 ms |
212 KB |
n = 8 |
13 |
Correct |
0 ms |
212 KB |
n = 8 |
14 |
Correct |
1 ms |
212 KB |
n = 8 |
15 |
Correct |
1 ms |
296 KB |
n = 8 |
16 |
Correct |
1 ms |
212 KB |
n = 8 |
17 |
Correct |
1 ms |
212 KB |
n = 8 |
18 |
Correct |
1 ms |
296 KB |
n = 8 |
19 |
Correct |
1 ms |
212 KB |
n = 3 |
20 |
Correct |
0 ms |
296 KB |
n = 7 |
21 |
Correct |
1 ms |
212 KB |
n = 8 |
22 |
Correct |
1 ms |
212 KB |
n = 8 |
23 |
Correct |
0 ms |
212 KB |
n = 8 |
24 |
Correct |
1 ms |
300 KB |
n = 8 |
25 |
Correct |
0 ms |
300 KB |
n = 8 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
n = 2 |
2 |
Correct |
1 ms |
212 KB |
n = 2 |
3 |
Correct |
0 ms |
212 KB |
n = 2 |
4 |
Correct |
0 ms |
212 KB |
n = 2 |
5 |
Correct |
0 ms |
212 KB |
n = 2 |
6 |
Correct |
0 ms |
212 KB |
n = 2 |
7 |
Correct |
0 ms |
212 KB |
n = 3 |
8 |
Correct |
0 ms |
212 KB |
n = 3 |
9 |
Correct |
0 ms |
212 KB |
n = 3 |
10 |
Correct |
1 ms |
212 KB |
n = 8 |
11 |
Correct |
0 ms |
212 KB |
n = 8 |
12 |
Correct |
0 ms |
212 KB |
n = 8 |
13 |
Correct |
0 ms |
212 KB |
n = 8 |
14 |
Correct |
1 ms |
212 KB |
n = 8 |
15 |
Correct |
1 ms |
296 KB |
n = 8 |
16 |
Correct |
1 ms |
212 KB |
n = 8 |
17 |
Correct |
1 ms |
212 KB |
n = 8 |
18 |
Correct |
1 ms |
296 KB |
n = 8 |
19 |
Correct |
1 ms |
212 KB |
n = 3 |
20 |
Correct |
0 ms |
296 KB |
n = 7 |
21 |
Correct |
1 ms |
212 KB |
n = 8 |
22 |
Correct |
1 ms |
212 KB |
n = 8 |
23 |
Correct |
0 ms |
212 KB |
n = 8 |
24 |
Correct |
1 ms |
300 KB |
n = 8 |
25 |
Correct |
0 ms |
300 KB |
n = 8 |
26 |
Correct |
0 ms |
212 KB |
n = 8 |
27 |
Correct |
1 ms |
212 KB |
n = 8 |
28 |
Correct |
1 ms |
212 KB |
n = 8 |
29 |
Correct |
0 ms |
212 KB |
n = 16 |
30 |
Correct |
0 ms |
212 KB |
n = 16 |
31 |
Correct |
1 ms |
212 KB |
n = 16 |
32 |
Correct |
1 ms |
212 KB |
n = 16 |
33 |
Correct |
1 ms |
212 KB |
n = 16 |
34 |
Correct |
1 ms |
304 KB |
n = 16 |
35 |
Correct |
1 ms |
212 KB |
n = 16 |
36 |
Correct |
1 ms |
212 KB |
n = 15 |
37 |
Correct |
1 ms |
296 KB |
n = 8 |
38 |
Correct |
1 ms |
212 KB |
n = 16 |
39 |
Correct |
1 ms |
212 KB |
n = 16 |
40 |
Correct |
1 ms |
340 KB |
n = 9 |
41 |
Correct |
1 ms |
296 KB |
n = 16 |
42 |
Correct |
1 ms |
304 KB |
n = 16 |
43 |
Correct |
1 ms |
212 KB |
n = 16 |
44 |
Correct |
1 ms |
300 KB |
n = 9 |
45 |
Correct |
1 ms |
212 KB |
n = 15 |
46 |
Correct |
1 ms |
256 KB |
n = 16 |
47 |
Correct |
1 ms |
212 KB |
n = 16 |
48 |
Correct |
1 ms |
296 KB |
n = 16 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
234 ms |
31852 KB |
n = 199999 |
2 |
Correct |
295 ms |
31820 KB |
n = 199991 |
3 |
Correct |
222 ms |
31784 KB |
n = 199993 |
4 |
Correct |
184 ms |
28020 KB |
n = 152076 |
5 |
Correct |
114 ms |
15516 KB |
n = 93249 |
6 |
Correct |
214 ms |
30636 KB |
n = 199910 |
7 |
Correct |
231 ms |
31784 KB |
n = 199999 |
8 |
Correct |
235 ms |
30764 KB |
n = 199997 |
9 |
Correct |
219 ms |
29584 KB |
n = 171294 |
10 |
Correct |
177 ms |
27200 KB |
n = 140872 |
11 |
Correct |
225 ms |
30764 KB |
n = 199886 |
12 |
Correct |
229 ms |
34992 KB |
n = 199996 |
13 |
Correct |
222 ms |
33940 KB |
n = 200000 |
14 |
Correct |
241 ms |
34716 KB |
n = 199998 |
15 |
Correct |
226 ms |
34588 KB |
n = 200000 |
16 |
Correct |
231 ms |
35172 KB |
n = 199998 |
17 |
Correct |
224 ms |
35644 KB |
n = 200000 |
18 |
Correct |
222 ms |
34760 KB |
n = 190000 |
19 |
Correct |
190 ms |
33584 KB |
n = 177777 |
20 |
Correct |
104 ms |
18032 KB |
n = 100000 |
21 |
Correct |
229 ms |
35744 KB |
n = 200000 |
22 |
Correct |
235 ms |
35756 KB |
n = 200000 |
23 |
Correct |
252 ms |
35648 KB |
n = 200000 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
n = 2 |
2 |
Correct |
1 ms |
212 KB |
n = 2 |
3 |
Correct |
0 ms |
212 KB |
n = 2 |
4 |
Correct |
0 ms |
212 KB |
n = 2 |
5 |
Correct |
0 ms |
212 KB |
n = 2 |
6 |
Correct |
0 ms |
212 KB |
n = 2 |
7 |
Correct |
0 ms |
212 KB |
n = 3 |
8 |
Correct |
0 ms |
212 KB |
n = 3 |
9 |
Correct |
0 ms |
212 KB |
n = 3 |
10 |
Correct |
1 ms |
212 KB |
n = 8 |
11 |
Correct |
0 ms |
212 KB |
n = 8 |
12 |
Correct |
0 ms |
212 KB |
n = 8 |
13 |
Correct |
0 ms |
212 KB |
n = 8 |
14 |
Correct |
1 ms |
212 KB |
n = 8 |
15 |
Correct |
1 ms |
296 KB |
n = 8 |
16 |
Correct |
1 ms |
212 KB |
n = 8 |
17 |
Correct |
1 ms |
212 KB |
n = 8 |
18 |
Correct |
1 ms |
296 KB |
n = 8 |
19 |
Correct |
1 ms |
212 KB |
n = 3 |
20 |
Correct |
0 ms |
296 KB |
n = 7 |
21 |
Correct |
1 ms |
212 KB |
n = 8 |
22 |
Correct |
1 ms |
212 KB |
n = 8 |
23 |
Correct |
0 ms |
212 KB |
n = 8 |
24 |
Correct |
1 ms |
300 KB |
n = 8 |
25 |
Correct |
0 ms |
300 KB |
n = 8 |
26 |
Correct |
0 ms |
212 KB |
n = 8 |
27 |
Correct |
1 ms |
212 KB |
n = 8 |
28 |
Correct |
1 ms |
212 KB |
n = 8 |
29 |
Correct |
0 ms |
212 KB |
n = 16 |
30 |
Correct |
0 ms |
212 KB |
n = 16 |
31 |
Correct |
1 ms |
212 KB |
n = 16 |
32 |
Correct |
1 ms |
212 KB |
n = 16 |
33 |
Correct |
1 ms |
212 KB |
n = 16 |
34 |
Correct |
1 ms |
304 KB |
n = 16 |
35 |
Correct |
1 ms |
212 KB |
n = 16 |
36 |
Correct |
1 ms |
212 KB |
n = 15 |
37 |
Correct |
1 ms |
296 KB |
n = 8 |
38 |
Correct |
1 ms |
212 KB |
n = 16 |
39 |
Correct |
1 ms |
212 KB |
n = 16 |
40 |
Correct |
1 ms |
340 KB |
n = 9 |
41 |
Correct |
1 ms |
296 KB |
n = 16 |
42 |
Correct |
1 ms |
304 KB |
n = 16 |
43 |
Correct |
1 ms |
212 KB |
n = 16 |
44 |
Correct |
1 ms |
300 KB |
n = 9 |
45 |
Correct |
1 ms |
212 KB |
n = 15 |
46 |
Correct |
1 ms |
256 KB |
n = 16 |
47 |
Correct |
1 ms |
212 KB |
n = 16 |
48 |
Correct |
1 ms |
296 KB |
n = 16 |
49 |
Correct |
234 ms |
31852 KB |
n = 199999 |
50 |
Correct |
295 ms |
31820 KB |
n = 199991 |
51 |
Correct |
222 ms |
31784 KB |
n = 199993 |
52 |
Correct |
184 ms |
28020 KB |
n = 152076 |
53 |
Correct |
114 ms |
15516 KB |
n = 93249 |
54 |
Correct |
214 ms |
30636 KB |
n = 199910 |
55 |
Correct |
231 ms |
31784 KB |
n = 199999 |
56 |
Correct |
235 ms |
30764 KB |
n = 199997 |
57 |
Correct |
219 ms |
29584 KB |
n = 171294 |
58 |
Correct |
177 ms |
27200 KB |
n = 140872 |
59 |
Correct |
225 ms |
30764 KB |
n = 199886 |
60 |
Correct |
229 ms |
34992 KB |
n = 199996 |
61 |
Correct |
222 ms |
33940 KB |
n = 200000 |
62 |
Correct |
241 ms |
34716 KB |
n = 199998 |
63 |
Correct |
226 ms |
34588 KB |
n = 200000 |
64 |
Correct |
231 ms |
35172 KB |
n = 199998 |
65 |
Correct |
224 ms |
35644 KB |
n = 200000 |
66 |
Correct |
222 ms |
34760 KB |
n = 190000 |
67 |
Correct |
190 ms |
33584 KB |
n = 177777 |
68 |
Correct |
104 ms |
18032 KB |
n = 100000 |
69 |
Correct |
229 ms |
35744 KB |
n = 200000 |
70 |
Correct |
235 ms |
35756 KB |
n = 200000 |
71 |
Correct |
252 ms |
35648 KB |
n = 200000 |
72 |
Correct |
238 ms |
35748 KB |
n = 200000 |
73 |
Correct |
264 ms |
35728 KB |
n = 200000 |
74 |
Correct |
220 ms |
35756 KB |
n = 200000 |
75 |
Correct |
224 ms |
35736 KB |
n = 200000 |
76 |
Correct |
224 ms |
35652 KB |
n = 200000 |
77 |
Correct |
170 ms |
26048 KB |
n = 200000 |
78 |
Correct |
167 ms |
26004 KB |
n = 200000 |
79 |
Correct |
226 ms |
33940 KB |
n = 184307 |
80 |
Correct |
77 ms |
15584 KB |
n = 76040 |
81 |
Correct |
204 ms |
33556 KB |
n = 199981 |
82 |
Correct |
259 ms |
34924 KB |
n = 199994 |
83 |
Correct |
204 ms |
33816 KB |
n = 199996 |
84 |
Correct |
222 ms |
34712 KB |
n = 199998 |
85 |
Correct |
216 ms |
34584 KB |
n = 200000 |
86 |
Correct |
246 ms |
35156 KB |
n = 199998 |
87 |
Correct |
212 ms |
35652 KB |
n = 200000 |
88 |
Correct |
240 ms |
35732 KB |
n = 200000 |
89 |
Correct |
224 ms |
35632 KB |
n = 200000 |
90 |
Correct |
230 ms |
35684 KB |
n = 200000 |
91 |
Correct |
281 ms |
35760 KB |
n = 200000 |
92 |
Correct |
237 ms |
35748 KB |
n = 200000 |