#include "railroad.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
const int infinity = 2e9;
const int MAX_N = 2e5 + 5;
vi vals;
inline int Val(int x) {
return lower_bound(all(vals), x) - vals.begin();
}
int add[2 * MAX_N];
struct Dsu {
vi par, sz;
Dsu() {}
Dsu(int n) {
par.resize(n), sz.resize(n, 1);
iota(all(par), 0);
}
int Find(int i) {
return par[i] == i ? i : par[i] = Find(par[i]);
}
bool Union(int a, int b) {
int pa = Find(a), pb = Find(b);
if (pa == pb) return false;
if (sz[pa] < sz[pb]) swap(pa, pb);
par[pb] = pa;
sz[pa] += sz[pb];
return true;
}
};
ll plan_roller_coaster(vi s, vi t) {
int n = s.size();
s.push_back(infinity), t.push_back(0);
for (int i = 0; i <= n; i++) vals.push_back(s[i]), vals.push_back(t[i]);
sort(all(vals));
vals.erase(unique(all(vals)), vals.end());
for (int &x : s) {
x = Val(x);
add[x]++;
}
for (int &x : t) {
x = Val(x);
add[x]--;
}
int sz = vals.size();
Dsu dsu(sz);
for (int i = 0; i <= n; i++) dsu.Union(s[i], t[i]);
ll ans = 0;
for (int i = 0, balance = 0; i < sz; i++) {
balance += add[i];
if (balance > 0) ans += balance * (vals[i + 1] - vals[i]);
if (balance) dsu.Union(i, i + 1);
}
vector<pair<ll, pii>> edges;
for (int i = 0; i < sz - 1; i++) {
edges.push_back({vals[i + 1] - vals[i], {i, i + 1}});
}
sort(all(edges));
for (auto [x, p] : edges) {
ans += x * dsu.Union(p.x, p.y);
}
return ans;
}
