#include <bits/stdc++.h>
#ifndef DEBUG
#include "railroad.h"
#endif
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1& x, T2 y) {
return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1& x, T2 y) {
return y > x ? (x = y, true) : false;
}
void debug_out() {
cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
cerr << ' ' << A;
debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
for (int i = 0; i < n; ++i) {
cerr << a[i] << ' ';
}
cerr << endl;
}
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
#define debug(...) 1337
#define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) {
for (auto& x : v) {
stream << x << ' ';
}
return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
return stream << p.first << ' ' << p.second;
}
const int inf = 1e9 + 1337;
namespace dsu {
vector<int> q;
void init(int n) {
q.assign(n, -1);
}
int gt(int x) {
return q[x] < 0 ? x : q[x] = gt(q[x]);
}
bool join(int x, int y) {
x = gt(x);
y = gt(y);
if (x == y) return false;
if (-q[x] < -q[y]) swap(x, y);
q[x] += q[y];
q[y] = x;
return true;
}
}
ll plan_roller_coaster(vector<int> s, vector<int> t) {
s.push_back(inf);
t.push_back(1);
int n = s.size();
vector<int> points;
for (int i = 0; i < n; ++i) {
points.push_back(s[i]);
points.push_back(t[i]);
}
sort(all(points));
points.resize(unique(all(points)) - points.begin());
int m = points.size();
auto compr = [&](int x) -> int {
return lower_bound(all(points), x) - points.begin();
};
dsu::init(m);
vector<int> cs(n), ct(n), bal(m + 1, 0);
for (int i = 0; i < n; ++i) {
cs[i] = compr(s[i]);
ct[i] = compr(t[i]);
dsu::join(cs[i], ct[i]);
++bal[cs[i]];
--bal[ct[i]];
}
ll ans = 0;
for (int j = 0; j < m; ++j) {
bal[j + 1] += bal[j];
if (bal[j] != 0) {
dsu::join(j, j + 1);
if (bal[j] > 0) {
ans += bal[j] * (ll)(points[j + 1] - points[j]);
}
}
}
vector<pli> edges;
for (int j = 0; j + 1 < m; ++j) {
if (dsu::gt(j) != dsu::gt(j + 1)) {
edges.emplace_back(points[j + 1] - points[j], j);
}
}
sort(all(edges));
for (auto& e : edges) {
ll w = e.fi;
int j = e.se;
if (dsu::join(j, j + 1)) {
ans += w;
}
}
return ans;
}
#ifdef DEBUG
int32_t main() {
#ifdef DEBUG
freopen("in", "r", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> s(n), t(n);
for (int i = 0; i < n; ++i) {
cin >> s[i] >> t[i];
}
cout << plan_roller_coaster(s, t) << '\n';
return 0;
}
#endif
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
n = 2 |
2 |
Correct |
1 ms |
204 KB |
n = 2 |
3 |
Correct |
1 ms |
204 KB |
n = 2 |
4 |
Correct |
1 ms |
204 KB |
n = 2 |
5 |
Correct |
1 ms |
208 KB |
n = 2 |
6 |
Correct |
1 ms |
204 KB |
n = 2 |
7 |
Correct |
1 ms |
292 KB |
n = 3 |
8 |
Correct |
1 ms |
204 KB |
n = 3 |
9 |
Correct |
1 ms |
204 KB |
n = 3 |
10 |
Correct |
1 ms |
204 KB |
n = 8 |
11 |
Correct |
1 ms |
204 KB |
n = 8 |
12 |
Correct |
1 ms |
204 KB |
n = 8 |
13 |
Correct |
1 ms |
204 KB |
n = 8 |
14 |
Correct |
1 ms |
204 KB |
n = 8 |
15 |
Correct |
1 ms |
204 KB |
n = 8 |
16 |
Correct |
1 ms |
204 KB |
n = 8 |
17 |
Correct |
1 ms |
204 KB |
n = 8 |
18 |
Correct |
1 ms |
204 KB |
n = 8 |
19 |
Correct |
1 ms |
204 KB |
n = 3 |
20 |
Correct |
1 ms |
296 KB |
n = 7 |
21 |
Correct |
1 ms |
204 KB |
n = 8 |
22 |
Correct |
1 ms |
204 KB |
n = 8 |
23 |
Correct |
1 ms |
204 KB |
n = 8 |
24 |
Correct |
1 ms |
204 KB |
n = 8 |
25 |
Correct |
1 ms |
292 KB |
n = 8 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
n = 2 |
2 |
Correct |
1 ms |
204 KB |
n = 2 |
3 |
Correct |
1 ms |
204 KB |
n = 2 |
4 |
Correct |
1 ms |
204 KB |
n = 2 |
5 |
Correct |
1 ms |
208 KB |
n = 2 |
6 |
Correct |
1 ms |
204 KB |
n = 2 |
7 |
Correct |
1 ms |
292 KB |
n = 3 |
8 |
Correct |
1 ms |
204 KB |
n = 3 |
9 |
Correct |
1 ms |
204 KB |
n = 3 |
10 |
Correct |
1 ms |
204 KB |
n = 8 |
11 |
Correct |
1 ms |
204 KB |
n = 8 |
12 |
Correct |
1 ms |
204 KB |
n = 8 |
13 |
Correct |
1 ms |
204 KB |
n = 8 |
14 |
Correct |
1 ms |
204 KB |
n = 8 |
15 |
Correct |
1 ms |
204 KB |
n = 8 |
16 |
Correct |
1 ms |
204 KB |
n = 8 |
17 |
Correct |
1 ms |
204 KB |
n = 8 |
18 |
Correct |
1 ms |
204 KB |
n = 8 |
19 |
Correct |
1 ms |
204 KB |
n = 3 |
20 |
Correct |
1 ms |
296 KB |
n = 7 |
21 |
Correct |
1 ms |
204 KB |
n = 8 |
22 |
Correct |
1 ms |
204 KB |
n = 8 |
23 |
Correct |
1 ms |
204 KB |
n = 8 |
24 |
Correct |
1 ms |
204 KB |
n = 8 |
25 |
Correct |
1 ms |
292 KB |
n = 8 |
26 |
Correct |
1 ms |
204 KB |
n = 8 |
27 |
Correct |
1 ms |
208 KB |
n = 8 |
28 |
Correct |
1 ms |
204 KB |
n = 8 |
29 |
Correct |
1 ms |
204 KB |
n = 16 |
30 |
Correct |
1 ms |
204 KB |
n = 16 |
31 |
Correct |
1 ms |
204 KB |
n = 16 |
32 |
Correct |
1 ms |
204 KB |
n = 16 |
33 |
Correct |
1 ms |
332 KB |
n = 16 |
34 |
Correct |
1 ms |
296 KB |
n = 16 |
35 |
Correct |
1 ms |
204 KB |
n = 16 |
36 |
Correct |
1 ms |
204 KB |
n = 15 |
37 |
Correct |
1 ms |
204 KB |
n = 8 |
38 |
Correct |
1 ms |
204 KB |
n = 16 |
39 |
Correct |
1 ms |
204 KB |
n = 16 |
40 |
Correct |
1 ms |
292 KB |
n = 9 |
41 |
Correct |
1 ms |
300 KB |
n = 16 |
42 |
Correct |
1 ms |
204 KB |
n = 16 |
43 |
Correct |
1 ms |
204 KB |
n = 16 |
44 |
Correct |
1 ms |
204 KB |
n = 9 |
45 |
Correct |
1 ms |
204 KB |
n = 15 |
46 |
Correct |
1 ms |
292 KB |
n = 16 |
47 |
Correct |
1 ms |
204 KB |
n = 16 |
48 |
Correct |
1 ms |
204 KB |
n = 16 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
183 ms |
13572 KB |
n = 199999 |
2 |
Correct |
185 ms |
13472 KB |
n = 199991 |
3 |
Correct |
180 ms |
13460 KB |
n = 199993 |
4 |
Correct |
134 ms |
9996 KB |
n = 152076 |
5 |
Correct |
79 ms |
6468 KB |
n = 93249 |
6 |
Correct |
165 ms |
11860 KB |
n = 199910 |
7 |
Correct |
168 ms |
12772 KB |
n = 199999 |
8 |
Correct |
161 ms |
11804 KB |
n = 199997 |
9 |
Correct |
154 ms |
11520 KB |
n = 171294 |
10 |
Correct |
126 ms |
9628 KB |
n = 140872 |
11 |
Correct |
165 ms |
11864 KB |
n = 199886 |
12 |
Correct |
169 ms |
12820 KB |
n = 199996 |
13 |
Correct |
164 ms |
12056 KB |
n = 200000 |
14 |
Correct |
175 ms |
14484 KB |
n = 199998 |
15 |
Correct |
173 ms |
14352 KB |
n = 200000 |
16 |
Correct |
179 ms |
14876 KB |
n = 199998 |
17 |
Correct |
185 ms |
13592 KB |
n = 200000 |
18 |
Correct |
176 ms |
12828 KB |
n = 190000 |
19 |
Correct |
150 ms |
12104 KB |
n = 177777 |
20 |
Correct |
83 ms |
6804 KB |
n = 100000 |
21 |
Correct |
176 ms |
13580 KB |
n = 200000 |
22 |
Correct |
209 ms |
17696 KB |
n = 200000 |
23 |
Correct |
225 ms |
13452 KB |
n = 200000 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
n = 2 |
2 |
Correct |
1 ms |
204 KB |
n = 2 |
3 |
Correct |
1 ms |
204 KB |
n = 2 |
4 |
Correct |
1 ms |
204 KB |
n = 2 |
5 |
Correct |
1 ms |
208 KB |
n = 2 |
6 |
Correct |
1 ms |
204 KB |
n = 2 |
7 |
Correct |
1 ms |
292 KB |
n = 3 |
8 |
Correct |
1 ms |
204 KB |
n = 3 |
9 |
Correct |
1 ms |
204 KB |
n = 3 |
10 |
Correct |
1 ms |
204 KB |
n = 8 |
11 |
Correct |
1 ms |
204 KB |
n = 8 |
12 |
Correct |
1 ms |
204 KB |
n = 8 |
13 |
Correct |
1 ms |
204 KB |
n = 8 |
14 |
Correct |
1 ms |
204 KB |
n = 8 |
15 |
Correct |
1 ms |
204 KB |
n = 8 |
16 |
Correct |
1 ms |
204 KB |
n = 8 |
17 |
Correct |
1 ms |
204 KB |
n = 8 |
18 |
Correct |
1 ms |
204 KB |
n = 8 |
19 |
Correct |
1 ms |
204 KB |
n = 3 |
20 |
Correct |
1 ms |
296 KB |
n = 7 |
21 |
Correct |
1 ms |
204 KB |
n = 8 |
22 |
Correct |
1 ms |
204 KB |
n = 8 |
23 |
Correct |
1 ms |
204 KB |
n = 8 |
24 |
Correct |
1 ms |
204 KB |
n = 8 |
25 |
Correct |
1 ms |
292 KB |
n = 8 |
26 |
Correct |
1 ms |
204 KB |
n = 8 |
27 |
Correct |
1 ms |
208 KB |
n = 8 |
28 |
Correct |
1 ms |
204 KB |
n = 8 |
29 |
Correct |
1 ms |
204 KB |
n = 16 |
30 |
Correct |
1 ms |
204 KB |
n = 16 |
31 |
Correct |
1 ms |
204 KB |
n = 16 |
32 |
Correct |
1 ms |
204 KB |
n = 16 |
33 |
Correct |
1 ms |
332 KB |
n = 16 |
34 |
Correct |
1 ms |
296 KB |
n = 16 |
35 |
Correct |
1 ms |
204 KB |
n = 16 |
36 |
Correct |
1 ms |
204 KB |
n = 15 |
37 |
Correct |
1 ms |
204 KB |
n = 8 |
38 |
Correct |
1 ms |
204 KB |
n = 16 |
39 |
Correct |
1 ms |
204 KB |
n = 16 |
40 |
Correct |
1 ms |
292 KB |
n = 9 |
41 |
Correct |
1 ms |
300 KB |
n = 16 |
42 |
Correct |
1 ms |
204 KB |
n = 16 |
43 |
Correct |
1 ms |
204 KB |
n = 16 |
44 |
Correct |
1 ms |
204 KB |
n = 9 |
45 |
Correct |
1 ms |
204 KB |
n = 15 |
46 |
Correct |
1 ms |
292 KB |
n = 16 |
47 |
Correct |
1 ms |
204 KB |
n = 16 |
48 |
Correct |
1 ms |
204 KB |
n = 16 |
49 |
Correct |
183 ms |
13572 KB |
n = 199999 |
50 |
Correct |
185 ms |
13472 KB |
n = 199991 |
51 |
Correct |
180 ms |
13460 KB |
n = 199993 |
52 |
Correct |
134 ms |
9996 KB |
n = 152076 |
53 |
Correct |
79 ms |
6468 KB |
n = 93249 |
54 |
Correct |
165 ms |
11860 KB |
n = 199910 |
55 |
Correct |
168 ms |
12772 KB |
n = 199999 |
56 |
Correct |
161 ms |
11804 KB |
n = 199997 |
57 |
Correct |
154 ms |
11520 KB |
n = 171294 |
58 |
Correct |
126 ms |
9628 KB |
n = 140872 |
59 |
Correct |
165 ms |
11864 KB |
n = 199886 |
60 |
Correct |
169 ms |
12820 KB |
n = 199996 |
61 |
Correct |
164 ms |
12056 KB |
n = 200000 |
62 |
Correct |
175 ms |
14484 KB |
n = 199998 |
63 |
Correct |
173 ms |
14352 KB |
n = 200000 |
64 |
Correct |
179 ms |
14876 KB |
n = 199998 |
65 |
Correct |
185 ms |
13592 KB |
n = 200000 |
66 |
Correct |
176 ms |
12828 KB |
n = 190000 |
67 |
Correct |
150 ms |
12104 KB |
n = 177777 |
68 |
Correct |
83 ms |
6804 KB |
n = 100000 |
69 |
Correct |
176 ms |
13580 KB |
n = 200000 |
70 |
Correct |
209 ms |
17696 KB |
n = 200000 |
71 |
Correct |
225 ms |
13452 KB |
n = 200000 |
72 |
Correct |
185 ms |
13452 KB |
n = 200000 |
73 |
Correct |
189 ms |
13576 KB |
n = 200000 |
74 |
Correct |
177 ms |
13484 KB |
n = 200000 |
75 |
Correct |
174 ms |
13460 KB |
n = 200000 |
76 |
Correct |
174 ms |
13688 KB |
n = 200000 |
77 |
Correct |
159 ms |
12068 KB |
n = 200000 |
78 |
Correct |
185 ms |
16168 KB |
n = 200000 |
79 |
Correct |
165 ms |
12436 KB |
n = 184307 |
80 |
Correct |
64 ms |
5228 KB |
n = 76040 |
81 |
Correct |
164 ms |
11936 KB |
n = 199981 |
82 |
Correct |
170 ms |
12828 KB |
n = 199994 |
83 |
Correct |
162 ms |
12084 KB |
n = 199996 |
84 |
Correct |
175 ms |
14484 KB |
n = 199998 |
85 |
Correct |
171 ms |
14368 KB |
n = 200000 |
86 |
Correct |
176 ms |
14928 KB |
n = 199998 |
87 |
Correct |
173 ms |
13600 KB |
n = 200000 |
88 |
Correct |
179 ms |
13452 KB |
n = 200000 |
89 |
Correct |
178 ms |
13568 KB |
n = 200000 |
90 |
Correct |
177 ms |
13456 KB |
n = 200000 |
91 |
Correct |
223 ms |
17784 KB |
n = 200000 |
92 |
Correct |
226 ms |
13472 KB |
n = 200000 |