#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int u, v, w;
Edge(int _u, int _v, int _w) {
u = _u;
v = _v;
w = _w;
}
bool operator < (const Edge &oth) {
return w < oth.w;
}
};
struct DSU {
int n;
vector<int> root, rnk;
DSU(int _n) {
n = _n;
root.assign(n, 0);
rnk.assign(n, 0);
iota(root.begin(), root.end(), 0);
}
int findRoot(int u) {
if (u == root[u])
return u;
return root[u] = findRoot(root[u]);
}
bool unite(int u, int v) {
u = findRoot(u);
v = findRoot(v);
if (u == v)
return 0;
if (rnk[u] < rnk[v])
swap(u, v);
root[v] = u;
rnk[u] += (rnk[u] == rnk[v]);
return 1;
}
};
long long plan_roller_coaster(vector<int> s, vector<int> t) {
int m = (int) s.size();
vector<int> xCoor;
for (int i = 0; i < m; i++) {
xCoor.push_back(s[i]);
xCoor.push_back(t[i]);
}
xCoor.push_back(1);
xCoor.push_back(1e9);
sort(xCoor.begin(), xCoor.end());
xCoor.resize(unique(xCoor.begin(), xCoor.end()) - xCoor.begin());
int nX = xCoor.size();
DSU dsu(nX);
vector<int> deg(nX, 0);
for (int i = 0; i < m; i++) {
s[i] = lower_bound(xCoor.begin(), xCoor.end(), s[i]) - xCoor.begin();
t[i] = lower_bound(xCoor.begin(), xCoor.end(), t[i]) - xCoor.begin();
deg[s[i]]--;
deg[t[i]]++;
dsu.unite(s[i], t[i]);
}
deg[0]++;
deg[nX - 1]--;
dsu.unite(0, nX - 1);
vector<int> outPos, inPos;
for (int i = 0; i < nX; i++) {
while (deg[i] > 0) {
outPos.push_back(i);
deg[i]--;
}
while (deg[i] < 0) {
inPos.push_back(i);
deg[i]++;
}
}
long long ans = 0;
vector<int> cnt(nX, 0);
for (int i = 0; i < (int) outPos.size(); i++) {
int u = outPos[i], v = inPos[i];
ans += max(0, xCoor[u] - xCoor[v]);
cnt[min(u, v)]++;
cnt[max(u, v)]--;
}
for (int i = 1; i < nX; i++)
cnt[i] += cnt[i - 1];
vector<Edge> edges;
for (int i = 0; i < nX - 1; i++)
if (cnt[i])
dsu.unite(i, i + 1);
else
edges.push_back(Edge(i, i + 1, xCoor[i + 1] - xCoor[i]));
sort(edges.begin(), edges.end());
for (Edge e : edges)
ans += dsu.unite(e.u, e.v) * e.w;
return ans;
}
