#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define MAX 404040
#define INF 1000000001
vector<int> all;
int deg[MAX];
int N;
int p[MAX];
int find(int x) {
if (p[x] == x) return x;
return p[x] = find(p[x]);
}
void uni(int x, int y) {
x = find(x);
y = find(y);
p[x] = y;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
N = s.size();
for (auto v : s) all.push_back(v);
for (auto v : t) all.push_back(v);
all.push_back(INF);
all.push_back(0);
sort(all.begin(), all.end());
all.erase(unique(all.begin(), all.end()), all.end());
int X = all.size();
int i;
for (i = 0; i < N; i++) p[i] = i;
for (auto& v : s) v = lower_bound(all.begin(), all.end(), v) - all.begin();
for (auto& v : t) v = lower_bound(all.begin(), all.end(), v) - all.begin();
for (i = 0; i < N; i++) {
deg[s[i]]--;
deg[t[i]]++;
uni(s[i], t[i]);
}
deg[0]++;
deg[X - 1]--;
ll ans = 0;
for (i = 1; i < X; i++) {
if (deg[i - 1]) {
uni(i - 1, i);
if (deg[i - 1] < 0) ans += 1ll * -deg[i - 1] * (all[i] - all[i - 1]);
deg[i] += deg[i - 1];
}
}
vector<pii> vpi;
for (i = 1; i < X; i++) vpi.emplace_back(all[i] - all[i - 1], i);
sort(vpi.begin(), vpi.end());
for (auto& [c, v] : vpi) {
if (find(v - 1) != find(v)) {
uni(v - 1, v);
ans += c;
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
n = 2 |
| 2 |
Correct |
1 ms |
312 KB |
n = 2 |
| 3 |
Correct |
1 ms |
304 KB |
n = 2 |
| 4 |
Correct |
0 ms |
212 KB |
n = 2 |
| 5 |
Correct |
1 ms |
308 KB |
n = 2 |
| 6 |
Correct |
1 ms |
304 KB |
n = 2 |
| 7 |
Correct |
0 ms |
212 KB |
n = 3 |
| 8 |
Correct |
1 ms |
212 KB |
n = 3 |
| 9 |
Correct |
1 ms |
212 KB |
n = 3 |
| 10 |
Correct |
1 ms |
308 KB |
n = 8 |
| 11 |
Incorrect |
1 ms |
212 KB |
answer is not correct: 187084041 instead of 189002015 |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
n = 2 |
| 2 |
Correct |
1 ms |
312 KB |
n = 2 |
| 3 |
Correct |
1 ms |
304 KB |
n = 2 |
| 4 |
Correct |
0 ms |
212 KB |
n = 2 |
| 5 |
Correct |
1 ms |
308 KB |
n = 2 |
| 6 |
Correct |
1 ms |
304 KB |
n = 2 |
| 7 |
Correct |
0 ms |
212 KB |
n = 3 |
| 8 |
Correct |
1 ms |
212 KB |
n = 3 |
| 9 |
Correct |
1 ms |
212 KB |
n = 3 |
| 10 |
Correct |
1 ms |
308 KB |
n = 8 |
| 11 |
Incorrect |
1 ms |
212 KB |
answer is not correct: 187084041 instead of 189002015 |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
208 ms |
16340 KB |
n = 199999 |
| 2 |
Correct |
203 ms |
16320 KB |
n = 199991 |
| 3 |
Correct |
200 ms |
16240 KB |
n = 199993 |
| 4 |
Correct |
151 ms |
13128 KB |
n = 152076 |
| 5 |
Correct |
87 ms |
8084 KB |
n = 93249 |
| 6 |
Correct |
181 ms |
14560 KB |
n = 199910 |
| 7 |
Correct |
195 ms |
15576 KB |
n = 199999 |
| 8 |
Correct |
193 ms |
14832 KB |
n = 199997 |
| 9 |
Correct |
192 ms |
14436 KB |
n = 171294 |
| 10 |
Correct |
144 ms |
12908 KB |
n = 140872 |
| 11 |
Correct |
181 ms |
14588 KB |
n = 199886 |
| 12 |
Correct |
198 ms |
15796 KB |
n = 199996 |
| 13 |
Correct |
194 ms |
15040 KB |
n = 200000 |
| 14 |
Correct |
189 ms |
16048 KB |
n = 199998 |
| 15 |
Correct |
194 ms |
15928 KB |
n = 200000 |
| 16 |
Correct |
204 ms |
16112 KB |
n = 199998 |
| 17 |
Correct |
195 ms |
16220 KB |
n = 200000 |
| 18 |
Correct |
180 ms |
15720 KB |
n = 190000 |
| 19 |
Correct |
169 ms |
15036 KB |
n = 177777 |
| 20 |
Correct |
92 ms |
8356 KB |
n = 100000 |
| 21 |
Correct |
201 ms |
16192 KB |
n = 200000 |
| 22 |
Correct |
202 ms |
16468 KB |
n = 200000 |
| 23 |
Correct |
190 ms |
16496 KB |
n = 200000 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
n = 2 |
| 2 |
Correct |
1 ms |
312 KB |
n = 2 |
| 3 |
Correct |
1 ms |
304 KB |
n = 2 |
| 4 |
Correct |
0 ms |
212 KB |
n = 2 |
| 5 |
Correct |
1 ms |
308 KB |
n = 2 |
| 6 |
Correct |
1 ms |
304 KB |
n = 2 |
| 7 |
Correct |
0 ms |
212 KB |
n = 3 |
| 8 |
Correct |
1 ms |
212 KB |
n = 3 |
| 9 |
Correct |
1 ms |
212 KB |
n = 3 |
| 10 |
Correct |
1 ms |
308 KB |
n = 8 |
| 11 |
Incorrect |
1 ms |
212 KB |
answer is not correct: 187084041 instead of 189002015 |
| 12 |
Halted |
0 ms |
0 KB |
- |
