#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> par;
void init(int n){
par.resize(n);
for(int i = 0; i < n; i++) par[i] = i;
}
int find(int i){
if(par[i] == i) return i;
else return par[i] = find(par[i]);
}
void merge(int a, int b){
a = find(a), b = find(b);
par[a] = b;
}
vector<vector<int>> g;
vector<int> comp;
int dfs_cnt = 0;
void dfs(int u){
comp[u] = dfs_cnt;
for(int v : g[u]){
if(comp[v] == -1) dfs(v);
}
}
ll plan_roller_coaster(vector<int> s, vector<int> t) {
s.push_back(int(1e9+1));
t.push_back(1);
int n = (int)s.size();
vector<pair<int, int>> v;
vector<pair<int, int>> edges;
for(int i = 0; i < n; i++){
v.emplace_back(s[i], 1);
v.emplace_back(t[i], -1);
edges.emplace_back(s[i], t[i]);
}
sort(v.begin(), v.end());
int last = 1;
int sum = 0;
ll ans = 0;
for(auto [p, change] : v){
if(p != last){
if(sum != 0) edges.emplace_back(last, p), edges.emplace_back(p, last);
ans += (ll)max(0, sum)*(p-last);
last = p;
}
sum += change;
}
set<int> nodes;
for(auto [u, v] : edges) nodes.insert(u), nodes.insert(v);
vector<int> vnode(nodes.begin(), nodes.end());
n = (int)nodes.size();
g.resize(n);
for(auto [u, v] : edges){
int a = int(find(vnode.begin(), vnode.end(), u)-vnode.begin());
int b = int(find(vnode.begin(), vnode.end(), v)-vnode.begin());
g[a].push_back(b);
}
comp.resize(n, -1);
for(int i = 0; i < n; i++){
if(comp[i] == -1) dfs(i), dfs_cnt++;
}
vector<tuple<int, int, int>> ed;
for(int i = 1; i < n; i++){
if(comp[i] != comp[i-1]){
ed.emplace_back(vnode[i]-vnode[i-1], comp[i], comp[i-1]);
}
}
sort(ed.begin(), ed.end());
init(dfs_cnt);
for(auto [c, a, b] : ed){
if(find(a) != find(b)){
ans += c;
merge(a, b);
}
}
return ans;
}
