#include "railroad.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
int n;
const int maxN = 4e5+5;
int sw[maxN];
vector<int> adj[maxN];
int s[maxN], t[maxN];
struct dsu
{
int par[maxN];
int cc;
dsu(int n = 0)
{
for(int i = 0; i< n; i++) par[i] = i;
cc = n;
}
int findset(int x)
{
if(x == par[x]) return x;
return par[x] = findset(par[x]);
}
void unionset(int x, int y)
{
int a = findset(x), b = findset(y);
if(a == b) return;
cc--;
par[a] = b;
}
};
dsu foo;
ll plan_roller_coaster(vector<int> S, vector<int> T)
{
n = S.size();
for(int i = 0; i< n; i++)
{
s[i] = S[i];
t[i] = T[i];
}
vector<int> all;
for(int i = 0; i< n; i++)
{
all.pb(s[i]); all.pb(t[i]);
}
all.pb(1); all.pb(1e9);
sort(all.begin(), all.end());
all.resize(unique(all.begin(), all.end())-all.begin());
foo = dsu( (int) all.size());
sw[0]++;
sw[all.size()-1]--;
adj[all.size()-1].pb(0);
foo.unionset(all.size()-1, 0);
for(int i = 0; i< n; i++)
{
int ss = lower_bound(all.begin(), all.end(), s[i])-all.begin();
int tt = lower_bound(all.begin(), all.end(), t[i])-all.begin();
sw[ss]--;
sw[tt]++;
adj[ss].pb(tt);
foo.unionset(ss, tt);
}
int run = 0;
ll base = 0;
for(int i = 0; i+1< (int) all.size(); i++)
{
run += sw[i];
if(run> 0)
{
adj[i].pb(i+1);
foo.unionset(i, i+1);
}
if(run< 0)
{
adj[i+1].pb(i);
base += 1LL*-run*(all[i+1]-all[i]);
foo.unionset(i+1, i);
}
}
vector< ii > edges;
for(int i = 0; i+1< (int) all.size(); i++)
{
edges.pb({all[i+1]-all[i], i});
}
sort(edges.begin(), edges.end());
for(ii kk : edges)
{
int w = kk.X, u = kk.Y;
int x = foo.findset(u), y = foo.findset(u+1);
if(x == y) continue;
foo.unionset(x, y);
base += w;
if(foo.cc == 1) break;
}
return base;
}
