| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1293588 | baotoan655 | Roller Coaster Railroad (IOI16_railroad) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;
const int inf = 1e9;
const int N = 4e5 + 5;
int fa[N], sz[N];
int root(int u) {
if(u == fa[u]) return u;
return fa[u] = root(fa[u]);
}
bool join(int u, int v) {
u = root(u), v = root(v);
if(u == v) return false;
if(sz[u] < sz[v]) swap(u, v);
sz[u] += sz[v];
fa[v] = u;
return true;
}
long long plan_roller_coaster(int n, int s[], int t[]) {
++n;
s[n - 1] = inf;
t[n - 1] = 1;
vector<int> zip;
long long ans = 0;
for(int i = 0; i < n; ++i) {
zip.emplace_back(s[i]);
zip.emplace_back(t[i]);
}
sort(zip.begin(), zip.end());
zip.resize(unique(zip.begin(), zip.end()) - zip.begin());
int m = zip.size();
vector<int> ps(m);
for(int i = 0; i < m; ++i) fa[i] = i, sz[i] = 1;
for(int i = 0; i < n; ++i) {
s[i] = lower_bound(zip.begin(), zip.end(), s[i]) - zip.begin();
t[i] = lower_bound(zip.begin(), zip.end(), t[i]) - zip.begin();
ps[s[i]]++;
ps[t[i]]--;
join(s[i], t[i]);
}
int pref = 0;
vector<pair<int, int>> ve;
for(int i = 0; i < m - 1; ++i) {
pref += ps[i];
int d = zip[i + 1] - zip[i];
ans += max(0LL, (long long) pref * d);
if(pref != 0) join(i, i + 1);
else {
ve.emplace_back(d, i);
}
}
sort(ve.begin(), ve.end());
for(auto [w, u] : ve) {
if(join(u, u + 1)) ans += w;
}
return ans;
}
//int main() {
// ios_base::sync_with_stdio(false);
// cin.tie(0), cout.tie(0);
//
// file("A") else file("task");
// int n;
// cin >> n;
// int s[n], t[n];
// for(int i = 0; i < n; ++i) cin >> s[i] >> t[i];
// cout << plan_roller_coaster(n, s, t) << '\n';
// return 0;
//}