#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << ": " << x << endl;
#define sep ' '
#define X first
#define Y second
const ll MAXN = 1e6 + 10;
const ll INF = 1e9 + 7;
int n, cnt[MAXN], par[MAXN];
vector<int> comp_vec;
int find(int v) {
return par[v] == v ? v : par[v] = find(par[v]);
}
inline bool unite(int u, int v) {
u = find(u), v = find(v);
if (u == v) return false;
par[u] = v;
return true;
}
inline int ind(int x) {
return lower_bound(all(comp_vec), x) - comp_vec.begin();
}
ll plan_roller_coaster(vector<int> s, vector<int> t) {
s.push_back(0);
t.push_back(1e9 + 7);
ll ans = 0;
for (int i = 0; i < int(s.size()); i++) {
comp_vec.push_back(s[i]);
comp_vec.push_back(t[i]);
}
sort(all(comp_vec));
comp_vec.resize(unique(all(comp_vec)) - comp_vec.begin());
for (int i = 0; i < int(s.size()); i++) {
cnt[ind(s[i])]++;
cnt[ind(t[i])]--;
}
int m = comp_vec.size();
for (int i = 0; i < m; i++) par[i] = i;
int tot = -1;
vector<pair<int, pll>> edges;
for (int i = 0; i < m - 1; i++) {
tot += cnt[i];
if (tot <= 0) {
unite(i, i + 1);
} else if (tot > 1) {
unite(i, i + 1);
ans += 1ll * (tot - 1) * (comp_vec[i + 1] - comp_vec[i]);
}
//cerr << tot << sep << comp_vec[i] << sep << ans << endl;
edges.push_back({comp_vec[i + 1] - comp_vec[i], {i, i + 1}});
}
sort(all(edges));
for (auto [x, e] : edges)
if (unite(e.X, e.Y)){
// cerr << e.X << ' ' << e.Y << ' ' << x << endl;
ans += x;
}
return ans/2;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
n = 2 |
2 |
Correct |
0 ms |
304 KB |
n = 2 |
3 |
Correct |
0 ms |
212 KB |
n = 2 |
4 |
Correct |
1 ms |
212 KB |
n = 2 |
5 |
Correct |
1 ms |
212 KB |
n = 2 |
6 |
Incorrect |
1 ms |
212 KB |
answer is not correct: 352992301 instead of 523688153 |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
n = 2 |
2 |
Correct |
0 ms |
304 KB |
n = 2 |
3 |
Correct |
0 ms |
212 KB |
n = 2 |
4 |
Correct |
1 ms |
212 KB |
n = 2 |
5 |
Correct |
1 ms |
212 KB |
n = 2 |
6 |
Incorrect |
1 ms |
212 KB |
answer is not correct: 352992301 instead of 523688153 |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
168 ms |
27456 KB |
n = 199999 |
2 |
Correct |
167 ms |
26692 KB |
n = 199991 |
3 |
Correct |
166 ms |
27580 KB |
n = 199993 |
4 |
Correct |
118 ms |
22692 KB |
n = 152076 |
5 |
Correct |
71 ms |
12996 KB |
n = 93249 |
6 |
Correct |
153 ms |
24140 KB |
n = 199910 |
7 |
Correct |
158 ms |
26480 KB |
n = 199999 |
8 |
Correct |
181 ms |
24204 KB |
n = 199997 |
9 |
Correct |
161 ms |
24020 KB |
n = 171294 |
10 |
Incorrect |
120 ms |
22328 KB |
answer is not correct: 1 instead of 0 |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
n = 2 |
2 |
Correct |
0 ms |
304 KB |
n = 2 |
3 |
Correct |
0 ms |
212 KB |
n = 2 |
4 |
Correct |
1 ms |
212 KB |
n = 2 |
5 |
Correct |
1 ms |
212 KB |
n = 2 |
6 |
Incorrect |
1 ms |
212 KB |
answer is not correct: 352992301 instead of 523688153 |
7 |
Halted |
0 ms |
0 KB |
- |