#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
#define pb push_back
#define f first
#define s second
namespace debug {
const int DEBUG = false;
template<class T1, class T2>
void pr(const pair<T1, T2> &x);
template<class T, size_t SZ>
void pr(const array<T, SZ> &x);
template<class T>
void pr(const vector<T> &x);
template<class T>
void pr(const set<T> &x);
template<class T1, class T2>
void pr(const map<T1, T2> &x);
template<class T>
void pr(const T &x) { if (DEBUG) cout << x; }
template<class T, class... Ts>
void pr(const T &first, const Ts &... rest) { pr(first), pr(rest...); }
template<class T1, class T2>
void pr(const pair<T1, T2> &x) { pr("{", x.f, ", ", x.s, "}"); }
template<class T>
void prIn(const T &x) {
pr("{");
bool fst = 1;
for (auto &a : x) {
pr(fst ? "" : ", ", a), fst = 0;
}
pr("}");
}
template<class T, size_t SZ>
void pr(const array<T, SZ> &x) { prIn(x); }
template<class T>
void pr(const vector<T> &x) { prIn(x); }
template<class T>
void pr(const set<T> &x) { prIn(x); }
template<class T1, class T2>
void pr(const map<T1, T2> &x) { prIn(x); }
void ps() { pr("\n"), cout << flush; }
template<class Arg, class... Args>
void ps(const Arg &first, const Args &... rest) {
pr(first, " ");
ps(rest...);
}
}
using namespace debug;
struct DSU {
vi anc;
void init(int N) {
anc.resize(N);
for (int i = 0; i < N; i++) {
anc[i] = i;
}
}
int fRt(int i) {
return anc[i] == i ? i : anc[i] = fRt(anc[i]);
}
bool merge(int a, int b) {
a = fRt(a), b = fRt(b);
if (a == b) {
return false;
}
anc[a] = b;
return true;
}
} dsu;
ll plan_roller_coaster(vi s, vi e) {
s.pb(1e9);
e.pb(1);
int N = s.size();
set<int> pts;
for (int i = 0; i < N; i++) {
pts.insert(s[i]);
pts.insert(e[i]);
}
int PS = pts.size();
map<int, int> pMap;
vi ptl;
int cP = 0;
for (int x : pts) {
pMap[x] = cP++;
ptl.pb(x);
}
for (int i = 0; i < N; i++) {
s[i] = pMap[s[i]];
e[i] = pMap[e[i]];
}
ps("mapped");
vi up(PS, 0);
vi down(PS, 0);
for (int i = 0; i < N; i++) {
if (s[i] < e[i]) {
up[s[i]]++;
up[e[i]]--;
} else {
down[e[i]]++;
down[s[i]]--;
}
}
int uSum = 0, dSum = 0;
for (int i = 0; i < PS; i++) {
uSum += up[i];
dSum += down[i];
up[i] = uSum;
down[i] = dSum;
}
ps("segmented");
ps(ptl);
ps(s);
ps(e);
dsu.init(PS);
ll cost = 0;
for (int i = 0; i < N; i++) {
ps("merge:", s[i], e[i]);
dsu.merge(s[i], e[i]);
}
for (int i = 0; i < PS - 1; i++) {
if (up[i] > down[i]) {
cost += (ll) (up[i] - down[i]) * (ptl[i + 1] - ptl[i]);
ps("merge:", i, i + 1);
dsu.merge(i, i + 1); // will fall through
}
if (up[i] < down[i]) {
ps("merge:", i, i + 1);
dsu.merge(i, i + 1); // will jump up
}
}
for (int i = 0; i < PS; i++) {
pr(dsu.fRt(i), " ");
}
ps();
vector<pi> mstE;
for (int i = 0; i < PS - 1; i++) {
mstE.pb({ptl[i + 1] - ptl[i], i});
}
sort(mstE.begin(), mstE.end());
for (pi x : mstE) {
int c1 = dsu.fRt(x.s);
int c2 = dsu.fRt(x.s + 1);
if (c1 != c2) {
dsu.merge(c1, c2);
cost += x.f;
}
}
return cost;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
n = 2 |
2 |
Correct |
2 ms |
376 KB |
n = 2 |
3 |
Correct |
2 ms |
256 KB |
n = 2 |
4 |
Correct |
2 ms |
256 KB |
n = 2 |
5 |
Correct |
2 ms |
376 KB |
n = 2 |
6 |
Correct |
2 ms |
252 KB |
n = 2 |
7 |
Correct |
2 ms |
256 KB |
n = 3 |
8 |
Correct |
2 ms |
252 KB |
n = 3 |
9 |
Correct |
2 ms |
256 KB |
n = 3 |
10 |
Correct |
2 ms |
256 KB |
n = 8 |
11 |
Correct |
2 ms |
256 KB |
n = 8 |
12 |
Correct |
2 ms |
376 KB |
n = 8 |
13 |
Correct |
2 ms |
256 KB |
n = 8 |
14 |
Correct |
2 ms |
256 KB |
n = 8 |
15 |
Correct |
2 ms |
252 KB |
n = 8 |
16 |
Correct |
2 ms |
256 KB |
n = 8 |
17 |
Correct |
2 ms |
376 KB |
n = 8 |
18 |
Correct |
2 ms |
256 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 |
356 KB |
n = 8 |
24 |
Correct |
3 ms |
376 KB |
n = 8 |
25 |
Correct |
2 ms |
256 KB |
n = 8 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
n = 2 |
2 |
Correct |
2 ms |
376 KB |
n = 2 |
3 |
Correct |
2 ms |
256 KB |
n = 2 |
4 |
Correct |
2 ms |
256 KB |
n = 2 |
5 |
Correct |
2 ms |
376 KB |
n = 2 |
6 |
Correct |
2 ms |
252 KB |
n = 2 |
7 |
Correct |
2 ms |
256 KB |
n = 3 |
8 |
Correct |
2 ms |
252 KB |
n = 3 |
9 |
Correct |
2 ms |
256 KB |
n = 3 |
10 |
Correct |
2 ms |
256 KB |
n = 8 |
11 |
Correct |
2 ms |
256 KB |
n = 8 |
12 |
Correct |
2 ms |
376 KB |
n = 8 |
13 |
Correct |
2 ms |
256 KB |
n = 8 |
14 |
Correct |
2 ms |
256 KB |
n = 8 |
15 |
Correct |
2 ms |
252 KB |
n = 8 |
16 |
Correct |
2 ms |
256 KB |
n = 8 |
17 |
Correct |
2 ms |
376 KB |
n = 8 |
18 |
Correct |
2 ms |
256 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 |
356 KB |
n = 8 |
24 |
Correct |
3 ms |
376 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 |
256 KB |
n = 16 |
31 |
Correct |
2 ms |
256 KB |
n = 16 |
32 |
Correct |
2 ms |
252 KB |
n = 16 |
33 |
Correct |
2 ms |
376 KB |
n = 16 |
34 |
Correct |
2 ms |
376 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 |
376 KB |
n = 9 |
41 |
Correct |
2 ms |
256 KB |
n = 16 |
42 |
Correct |
2 ms |
256 KB |
n = 16 |
43 |
Correct |
2 ms |
256 KB |
n = 16 |
44 |
Correct |
2 ms |
256 KB |
n = 9 |
45 |
Correct |
2 ms |
256 KB |
n = 15 |
46 |
Correct |
2 ms |
376 KB |
n = 16 |
47 |
Correct |
2 ms |
376 KB |
n = 16 |
48 |
Correct |
2 ms |
376 KB |
n = 16 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1012 ms |
55480 KB |
n = 199999 |
2 |
Correct |
1065 ms |
55576 KB |
n = 199991 |
3 |
Correct |
1028 ms |
55388 KB |
n = 199993 |
4 |
Correct |
776 ms |
42976 KB |
n = 152076 |
5 |
Correct |
410 ms |
26312 KB |
n = 93249 |
6 |
Correct |
844 ms |
46440 KB |
n = 199910 |
7 |
Correct |
867 ms |
54380 KB |
n = 199999 |
8 |
Correct |
736 ms |
47244 KB |
n = 199997 |
9 |
Correct |
866 ms |
48076 KB |
n = 171294 |
10 |
Correct |
687 ms |
40416 KB |
n = 140872 |
11 |
Correct |
823 ms |
47056 KB |
n = 199886 |
12 |
Correct |
861 ms |
54812 KB |
n = 199996 |
13 |
Correct |
780 ms |
49020 KB |
n = 200000 |
14 |
Correct |
821 ms |
55632 KB |
n = 199998 |
15 |
Correct |
833 ms |
54224 KB |
n = 200000 |
16 |
Correct |
831 ms |
55852 KB |
n = 199998 |
17 |
Correct |
979 ms |
58576 KB |
n = 200000 |
18 |
Correct |
1064 ms |
53208 KB |
n = 190000 |
19 |
Correct |
901 ms |
52612 KB |
n = 177777 |
20 |
Correct |
436 ms |
28004 KB |
n = 100000 |
21 |
Correct |
941 ms |
55380 KB |
n = 200000 |
22 |
Correct |
943 ms |
55504 KB |
n = 200000 |
23 |
Correct |
1108 ms |
55444 KB |
n = 200000 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
n = 2 |
2 |
Correct |
2 ms |
376 KB |
n = 2 |
3 |
Correct |
2 ms |
256 KB |
n = 2 |
4 |
Correct |
2 ms |
256 KB |
n = 2 |
5 |
Correct |
2 ms |
376 KB |
n = 2 |
6 |
Correct |
2 ms |
252 KB |
n = 2 |
7 |
Correct |
2 ms |
256 KB |
n = 3 |
8 |
Correct |
2 ms |
252 KB |
n = 3 |
9 |
Correct |
2 ms |
256 KB |
n = 3 |
10 |
Correct |
2 ms |
256 KB |
n = 8 |
11 |
Correct |
2 ms |
256 KB |
n = 8 |
12 |
Correct |
2 ms |
376 KB |
n = 8 |
13 |
Correct |
2 ms |
256 KB |
n = 8 |
14 |
Correct |
2 ms |
256 KB |
n = 8 |
15 |
Correct |
2 ms |
252 KB |
n = 8 |
16 |
Correct |
2 ms |
256 KB |
n = 8 |
17 |
Correct |
2 ms |
376 KB |
n = 8 |
18 |
Correct |
2 ms |
256 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 |
356 KB |
n = 8 |
24 |
Correct |
3 ms |
376 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 |
256 KB |
n = 16 |
31 |
Correct |
2 ms |
256 KB |
n = 16 |
32 |
Correct |
2 ms |
252 KB |
n = 16 |
33 |
Correct |
2 ms |
376 KB |
n = 16 |
34 |
Correct |
2 ms |
376 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 |
376 KB |
n = 9 |
41 |
Correct |
2 ms |
256 KB |
n = 16 |
42 |
Correct |
2 ms |
256 KB |
n = 16 |
43 |
Correct |
2 ms |
256 KB |
n = 16 |
44 |
Correct |
2 ms |
256 KB |
n = 9 |
45 |
Correct |
2 ms |
256 KB |
n = 15 |
46 |
Correct |
2 ms |
376 KB |
n = 16 |
47 |
Correct |
2 ms |
376 KB |
n = 16 |
48 |
Correct |
2 ms |
376 KB |
n = 16 |
49 |
Correct |
1012 ms |
55480 KB |
n = 199999 |
50 |
Correct |
1065 ms |
55576 KB |
n = 199991 |
51 |
Correct |
1028 ms |
55388 KB |
n = 199993 |
52 |
Correct |
776 ms |
42976 KB |
n = 152076 |
53 |
Correct |
410 ms |
26312 KB |
n = 93249 |
54 |
Correct |
844 ms |
46440 KB |
n = 199910 |
55 |
Correct |
867 ms |
54380 KB |
n = 199999 |
56 |
Correct |
736 ms |
47244 KB |
n = 199997 |
57 |
Correct |
866 ms |
48076 KB |
n = 171294 |
58 |
Correct |
687 ms |
40416 KB |
n = 140872 |
59 |
Correct |
823 ms |
47056 KB |
n = 199886 |
60 |
Correct |
861 ms |
54812 KB |
n = 199996 |
61 |
Correct |
780 ms |
49020 KB |
n = 200000 |
62 |
Correct |
821 ms |
55632 KB |
n = 199998 |
63 |
Correct |
833 ms |
54224 KB |
n = 200000 |
64 |
Correct |
831 ms |
55852 KB |
n = 199998 |
65 |
Correct |
979 ms |
58576 KB |
n = 200000 |
66 |
Correct |
1064 ms |
53208 KB |
n = 190000 |
67 |
Correct |
901 ms |
52612 KB |
n = 177777 |
68 |
Correct |
436 ms |
28004 KB |
n = 100000 |
69 |
Correct |
941 ms |
55380 KB |
n = 200000 |
70 |
Correct |
943 ms |
55504 KB |
n = 200000 |
71 |
Correct |
1108 ms |
55444 KB |
n = 200000 |
72 |
Correct |
1129 ms |
55456 KB |
n = 200000 |
73 |
Correct |
1048 ms |
55576 KB |
n = 200000 |
74 |
Correct |
1060 ms |
55488 KB |
n = 200000 |
75 |
Correct |
986 ms |
55404 KB |
n = 200000 |
76 |
Correct |
991 ms |
55448 KB |
n = 200000 |
77 |
Correct |
517 ms |
35536 KB |
n = 200000 |
78 |
Correct |
552 ms |
32344 KB |
n = 200000 |
79 |
Correct |
965 ms |
51280 KB |
n = 184307 |
80 |
Correct |
306 ms |
21916 KB |
n = 76040 |
81 |
Correct |
830 ms |
47056 KB |
n = 199981 |
82 |
Correct |
870 ms |
54768 KB |
n = 199994 |
83 |
Correct |
819 ms |
48976 KB |
n = 199996 |
84 |
Correct |
806 ms |
55632 KB |
n = 199998 |
85 |
Correct |
822 ms |
54224 KB |
n = 200000 |
86 |
Correct |
845 ms |
55888 KB |
n = 199998 |
87 |
Correct |
973 ms |
58732 KB |
n = 200000 |
88 |
Correct |
992 ms |
56040 KB |
n = 200000 |
89 |
Correct |
969 ms |
58668 KB |
n = 200000 |
90 |
Correct |
961 ms |
55480 KB |
n = 200000 |
91 |
Correct |
933 ms |
55556 KB |
n = 200000 |
92 |
Correct |
983 ms |
55452 KB |
n = 200000 |