#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int maxn = 4e5+10;
struct DSU {
int pai[maxn], peso[maxn];
DSU() { for(int i = 0; i < maxn; i++) pai[i] = i, peso[i] = 1; }
int find(int x) { return pai[x] == x ? x : pai[x] = find(pai[x]); }
void join(int a, int b) {
a = find(a), b = find(b);
if(a == b) return;
if(peso[a] < peso[b])
swap(a, b);
pai[b] = a;
peso[a] += peso[b];
}
} dsu;
map<int,int> qtd;
struct Itv { int l, r; bool operator<(const Itv& o) { return r-l > o.r-o.l; } };
vector<Itv> itv;
int pai[maxn];
bool vis[maxn];
long long plan_roller_coaster(vector<int> s, vector<int> t) {
int n = (int) s.size();
long long ans = 0;
for(int i = 0; i < n; i++) {
qtd[s[i]]++, qtd[t[i]]--;
itv.push_back({min(s[i], t[i]), max(s[i], t[i])});
}
for(auto it = qtd.begin(); it != qtd.end(); ++it) {
if(it != qtd.begin())
it->second += prev(it)->second;
if(it->second != 1 && next(it) != qtd.end()) {
itv.push_back({it->first, next(it)->first});
if(it->second > 1)
ans += 1ll * (it->second-1) * (next(it)->first - it->first);
}
}
// agora que eu tenho todos os intervalos, tenho que checar as intersecções
sort(itv.begin(), itv.end()); // ordeno pelo de maior tamanho
int coord = 0;
for(auto& it : qtd)
it.second = ++coord;
iota(pai+1, pai+coord+1, 1); // todo mundo começa apontando pro próximo
for(auto [l, r] : itv) {
l = qtd[l], r = qtd[r];
vis[l] = 1, vis[r] = 1;
while(l < r) {
if(vis[l])
dsu.join(l, r);
int nxt = pai[l];
pai[l] = r;
l = nxt;
}
}
vector<array<int,3>> edges;
vector<int> points;
for(auto [l, r] : itv)
points.push_back(l), points.push_back(r);
sort(points.begin(), points.end());
for(int i = 1; i < points.size(); i++) {
int eu = dsu.find(qtd[points[i]]), ant = dsu.find(qtd[points[i-1]]);
if(eu != ans)
edges.push_back({points[i] - points[i-1], eu, ant});
}
sort(edges.begin(), edges.end());
for(auto [sz, x, y] : edges)
if(dsu.find(x) != dsu.find(y))
ans += sz, dsu.join(x, y);
return ans;
}
Compilation message
railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:78:19: 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 < points.size(); i++) {
| ~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3404 KB |
n = 2 |
2 |
Correct |
2 ms |
3404 KB |
n = 2 |
3 |
Correct |
2 ms |
3404 KB |
n = 2 |
4 |
Correct |
2 ms |
3404 KB |
n = 2 |
5 |
Correct |
2 ms |
3404 KB |
n = 2 |
6 |
Correct |
2 ms |
3404 KB |
n = 2 |
7 |
Correct |
2 ms |
3404 KB |
n = 3 |
8 |
Correct |
2 ms |
3404 KB |
n = 3 |
9 |
Correct |
2 ms |
3404 KB |
n = 3 |
10 |
Correct |
2 ms |
3404 KB |
n = 8 |
11 |
Correct |
2 ms |
3404 KB |
n = 8 |
12 |
Correct |
2 ms |
3404 KB |
n = 8 |
13 |
Correct |
2 ms |
3404 KB |
n = 8 |
14 |
Correct |
2 ms |
3420 KB |
n = 8 |
15 |
Correct |
2 ms |
3404 KB |
n = 8 |
16 |
Correct |
2 ms |
3404 KB |
n = 8 |
17 |
Correct |
2 ms |
3404 KB |
n = 8 |
18 |
Correct |
2 ms |
3404 KB |
n = 8 |
19 |
Correct |
2 ms |
3404 KB |
n = 3 |
20 |
Correct |
2 ms |
3408 KB |
n = 7 |
21 |
Correct |
2 ms |
3404 KB |
n = 8 |
22 |
Correct |
2 ms |
3404 KB |
n = 8 |
23 |
Correct |
2 ms |
3404 KB |
n = 8 |
24 |
Correct |
2 ms |
3404 KB |
n = 8 |
25 |
Correct |
2 ms |
3404 KB |
n = 8 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3404 KB |
n = 2 |
2 |
Correct |
2 ms |
3404 KB |
n = 2 |
3 |
Correct |
2 ms |
3404 KB |
n = 2 |
4 |
Correct |
2 ms |
3404 KB |
n = 2 |
5 |
Correct |
2 ms |
3404 KB |
n = 2 |
6 |
Correct |
2 ms |
3404 KB |
n = 2 |
7 |
Correct |
2 ms |
3404 KB |
n = 3 |
8 |
Correct |
2 ms |
3404 KB |
n = 3 |
9 |
Correct |
2 ms |
3404 KB |
n = 3 |
10 |
Correct |
2 ms |
3404 KB |
n = 8 |
11 |
Correct |
2 ms |
3404 KB |
n = 8 |
12 |
Correct |
2 ms |
3404 KB |
n = 8 |
13 |
Correct |
2 ms |
3404 KB |
n = 8 |
14 |
Correct |
2 ms |
3420 KB |
n = 8 |
15 |
Correct |
2 ms |
3404 KB |
n = 8 |
16 |
Correct |
2 ms |
3404 KB |
n = 8 |
17 |
Correct |
2 ms |
3404 KB |
n = 8 |
18 |
Correct |
2 ms |
3404 KB |
n = 8 |
19 |
Correct |
2 ms |
3404 KB |
n = 3 |
20 |
Correct |
2 ms |
3408 KB |
n = 7 |
21 |
Correct |
2 ms |
3404 KB |
n = 8 |
22 |
Correct |
2 ms |
3404 KB |
n = 8 |
23 |
Correct |
2 ms |
3404 KB |
n = 8 |
24 |
Correct |
2 ms |
3404 KB |
n = 8 |
25 |
Correct |
2 ms |
3404 KB |
n = 8 |
26 |
Correct |
2 ms |
3404 KB |
n = 8 |
27 |
Correct |
2 ms |
3424 KB |
n = 8 |
28 |
Correct |
2 ms |
3404 KB |
n = 8 |
29 |
Correct |
2 ms |
3404 KB |
n = 16 |
30 |
Correct |
2 ms |
3404 KB |
n = 16 |
31 |
Correct |
2 ms |
3404 KB |
n = 16 |
32 |
Correct |
2 ms |
3404 KB |
n = 16 |
33 |
Correct |
2 ms |
3404 KB |
n = 16 |
34 |
Correct |
2 ms |
3404 KB |
n = 16 |
35 |
Correct |
2 ms |
3404 KB |
n = 16 |
36 |
Correct |
2 ms |
3404 KB |
n = 15 |
37 |
Correct |
2 ms |
3404 KB |
n = 8 |
38 |
Correct |
2 ms |
3404 KB |
n = 16 |
39 |
Correct |
2 ms |
3404 KB |
n = 16 |
40 |
Correct |
2 ms |
3404 KB |
n = 9 |
41 |
Correct |
2 ms |
3404 KB |
n = 16 |
42 |
Correct |
2 ms |
3404 KB |
n = 16 |
43 |
Correct |
2 ms |
3404 KB |
n = 16 |
44 |
Correct |
2 ms |
3404 KB |
n = 9 |
45 |
Correct |
2 ms |
3404 KB |
n = 15 |
46 |
Correct |
2 ms |
3404 KB |
n = 16 |
47 |
Correct |
2 ms |
3404 KB |
n = 16 |
48 |
Correct |
2 ms |
3404 KB |
n = 16 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1417 ms |
67384 KB |
n = 199999 |
2 |
Correct |
1407 ms |
67432 KB |
n = 199991 |
3 |
Correct |
1400 ms |
67400 KB |
n = 199993 |
4 |
Correct |
959 ms |
44020 KB |
n = 152076 |
5 |
Correct |
507 ms |
34344 KB |
n = 93249 |
6 |
Correct |
969 ms |
62516 KB |
n = 199910 |
7 |
Correct |
1204 ms |
66856 KB |
n = 199999 |
8 |
Correct |
927 ms |
62796 KB |
n = 199997 |
9 |
Correct |
1129 ms |
47204 KB |
n = 171294 |
10 |
Correct |
890 ms |
42264 KB |
n = 140872 |
11 |
Correct |
989 ms |
63004 KB |
n = 199886 |
12 |
Correct |
1173 ms |
66756 KB |
n = 199996 |
13 |
Correct |
961 ms |
63384 KB |
n = 200000 |
14 |
Correct |
927 ms |
49308 KB |
n = 199998 |
15 |
Correct |
912 ms |
48844 KB |
n = 200000 |
16 |
Correct |
984 ms |
49748 KB |
n = 199998 |
17 |
Correct |
1155 ms |
67388 KB |
n = 200000 |
18 |
Correct |
1111 ms |
65744 KB |
n = 190000 |
19 |
Correct |
1006 ms |
63768 KB |
n = 177777 |
20 |
Correct |
501 ms |
35432 KB |
n = 100000 |
21 |
Correct |
1244 ms |
67424 KB |
n = 200000 |
22 |
Correct |
849 ms |
48860 KB |
n = 200000 |
23 |
Correct |
962 ms |
48852 KB |
n = 200000 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3404 KB |
n = 2 |
2 |
Correct |
2 ms |
3404 KB |
n = 2 |
3 |
Correct |
2 ms |
3404 KB |
n = 2 |
4 |
Correct |
2 ms |
3404 KB |
n = 2 |
5 |
Correct |
2 ms |
3404 KB |
n = 2 |
6 |
Correct |
2 ms |
3404 KB |
n = 2 |
7 |
Correct |
2 ms |
3404 KB |
n = 3 |
8 |
Correct |
2 ms |
3404 KB |
n = 3 |
9 |
Correct |
2 ms |
3404 KB |
n = 3 |
10 |
Correct |
2 ms |
3404 KB |
n = 8 |
11 |
Correct |
2 ms |
3404 KB |
n = 8 |
12 |
Correct |
2 ms |
3404 KB |
n = 8 |
13 |
Correct |
2 ms |
3404 KB |
n = 8 |
14 |
Correct |
2 ms |
3420 KB |
n = 8 |
15 |
Correct |
2 ms |
3404 KB |
n = 8 |
16 |
Correct |
2 ms |
3404 KB |
n = 8 |
17 |
Correct |
2 ms |
3404 KB |
n = 8 |
18 |
Correct |
2 ms |
3404 KB |
n = 8 |
19 |
Correct |
2 ms |
3404 KB |
n = 3 |
20 |
Correct |
2 ms |
3408 KB |
n = 7 |
21 |
Correct |
2 ms |
3404 KB |
n = 8 |
22 |
Correct |
2 ms |
3404 KB |
n = 8 |
23 |
Correct |
2 ms |
3404 KB |
n = 8 |
24 |
Correct |
2 ms |
3404 KB |
n = 8 |
25 |
Correct |
2 ms |
3404 KB |
n = 8 |
26 |
Correct |
2 ms |
3404 KB |
n = 8 |
27 |
Correct |
2 ms |
3424 KB |
n = 8 |
28 |
Correct |
2 ms |
3404 KB |
n = 8 |
29 |
Correct |
2 ms |
3404 KB |
n = 16 |
30 |
Correct |
2 ms |
3404 KB |
n = 16 |
31 |
Correct |
2 ms |
3404 KB |
n = 16 |
32 |
Correct |
2 ms |
3404 KB |
n = 16 |
33 |
Correct |
2 ms |
3404 KB |
n = 16 |
34 |
Correct |
2 ms |
3404 KB |
n = 16 |
35 |
Correct |
2 ms |
3404 KB |
n = 16 |
36 |
Correct |
2 ms |
3404 KB |
n = 15 |
37 |
Correct |
2 ms |
3404 KB |
n = 8 |
38 |
Correct |
2 ms |
3404 KB |
n = 16 |
39 |
Correct |
2 ms |
3404 KB |
n = 16 |
40 |
Correct |
2 ms |
3404 KB |
n = 9 |
41 |
Correct |
2 ms |
3404 KB |
n = 16 |
42 |
Correct |
2 ms |
3404 KB |
n = 16 |
43 |
Correct |
2 ms |
3404 KB |
n = 16 |
44 |
Correct |
2 ms |
3404 KB |
n = 9 |
45 |
Correct |
2 ms |
3404 KB |
n = 15 |
46 |
Correct |
2 ms |
3404 KB |
n = 16 |
47 |
Correct |
2 ms |
3404 KB |
n = 16 |
48 |
Correct |
2 ms |
3404 KB |
n = 16 |
49 |
Correct |
1417 ms |
67384 KB |
n = 199999 |
50 |
Correct |
1407 ms |
67432 KB |
n = 199991 |
51 |
Correct |
1400 ms |
67400 KB |
n = 199993 |
52 |
Correct |
959 ms |
44020 KB |
n = 152076 |
53 |
Correct |
507 ms |
34344 KB |
n = 93249 |
54 |
Correct |
969 ms |
62516 KB |
n = 199910 |
55 |
Correct |
1204 ms |
66856 KB |
n = 199999 |
56 |
Correct |
927 ms |
62796 KB |
n = 199997 |
57 |
Correct |
1129 ms |
47204 KB |
n = 171294 |
58 |
Correct |
890 ms |
42264 KB |
n = 140872 |
59 |
Correct |
989 ms |
63004 KB |
n = 199886 |
60 |
Correct |
1173 ms |
66756 KB |
n = 199996 |
61 |
Correct |
961 ms |
63384 KB |
n = 200000 |
62 |
Correct |
927 ms |
49308 KB |
n = 199998 |
63 |
Correct |
912 ms |
48844 KB |
n = 200000 |
64 |
Correct |
984 ms |
49748 KB |
n = 199998 |
65 |
Correct |
1155 ms |
67388 KB |
n = 200000 |
66 |
Correct |
1111 ms |
65744 KB |
n = 190000 |
67 |
Correct |
1006 ms |
63768 KB |
n = 177777 |
68 |
Correct |
501 ms |
35432 KB |
n = 100000 |
69 |
Correct |
1244 ms |
67424 KB |
n = 200000 |
70 |
Correct |
849 ms |
48860 KB |
n = 200000 |
71 |
Correct |
962 ms |
48852 KB |
n = 200000 |
72 |
Correct |
1372 ms |
67596 KB |
n = 200000 |
73 |
Correct |
1414 ms |
67648 KB |
n = 200000 |
74 |
Correct |
1398 ms |
67500 KB |
n = 200000 |
75 |
Correct |
1136 ms |
67556 KB |
n = 200000 |
76 |
Correct |
1105 ms |
67560 KB |
n = 200000 |
77 |
Correct |
656 ms |
38624 KB |
n = 200000 |
78 |
Correct |
418 ms |
27888 KB |
n = 200000 |
79 |
Correct |
1225 ms |
64896 KB |
n = 184307 |
80 |
Correct |
377 ms |
23856 KB |
n = 76040 |
81 |
Correct |
984 ms |
63144 KB |
n = 199981 |
82 |
Correct |
1164 ms |
66820 KB |
n = 199994 |
83 |
Correct |
933 ms |
63628 KB |
n = 199996 |
84 |
Correct |
939 ms |
49520 KB |
n = 199998 |
85 |
Correct |
925 ms |
49004 KB |
n = 200000 |
86 |
Correct |
979 ms |
49696 KB |
n = 199998 |
87 |
Correct |
1136 ms |
67536 KB |
n = 200000 |
88 |
Correct |
1149 ms |
67500 KB |
n = 200000 |
89 |
Correct |
1144 ms |
67688 KB |
n = 200000 |
90 |
Correct |
1184 ms |
67548 KB |
n = 200000 |
91 |
Correct |
851 ms |
49052 KB |
n = 200000 |
92 |
Correct |
954 ms |
49024 KB |
n = 200000 |