#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> rep, sizes;
int find(int u){
if (u == rep[u]) return u;
rep[u] = find(rep[u]);
return rep[u];
}
bool uni(int a, int b){
a = find(a);
b = find(b);
if (a == b) return false;
if (sizes[a] < sizes[b]) swap(a, b);
rep[b] = a;
sizes[a] += sizes[b];
return true;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
s.push_back(1e9);
t.push_back(1);
int n = (int) s.size();
set<int> points;
int np = 0;
vector<int> v = {-1};
map<int, int> idx;
for (int i=0; i<n; i++){
points.insert(s[i]);
points.insert(t[i]);
}
for (int x : points){
v.push_back(x);
idx[x] = np++;
}
//vector<vector<int>> graph(np);
rep = sizes = vector<int>(np);
iota(rep.begin(), rep.end(), 0);
//multiset<pair<int, bool>> segment_ends; // speed, begin(1)/end(0)
vector<int> balance_change(np);
vector<pair<int, int>> edges;
for (int i=0; i<n; i++){
edges.push_back({idx[s[i]], idx[t[i]]});
uni(idx[s[i]], idx[t[i]]);
balance_change[idx[s[i]]]++;
balance_change[idx[t[i]]]--;
}
//for (auto[k, v] : idx) cerr << k << ": " << v << endl;
/*for (int x : balance_change) cerr << x << " ";
cerr << endl;
for (int i=0; i<np; i++) cerr << find(i) << " ";
cerr << endl;
for (auto[u, v] : edges) cerr << u << " " << v << endl;
*/
ll res = 0;
ll balance = balance_change[0]; // zu viele nach rechts: positiv, zu viele nach links: negativ
vector<tuple<int, int, int>> possible_edges;
for (int i=1; i<np; i++){
//cerr << i << ": " << balance << endl;
if (balance > 0){
res += (balance * (v[i] - v[i-1]));
edges.push_back({i, i-1});
uni(i, i-1);
}
if (balance < 0){
edges.push_back({i-1, i});
uni(i, i-1);
}
possible_edges.push_back({v[i] - v[i-1], i, i-1});
balance += balance_change[i];
}
sort(possible_edges.begin(), possible_edges.end());
for (auto[c, a, b] : possible_edges){
//cerr << c << " " << a << " " << b << endl;
res += c * uni(a, b);
}
//for (int i=0; i<np; i++) cerr << find(i) << " ";
//cerr << endl;
//for (auto[u, v] : edges) cerr << u << " " << v << endl;
return res;
}
