#include "railroad.h"
#include <map>
#include <set>
#include <utility>
#include <vector>
#include <algorithm>
#include <cassert>
#define MAXN 200005
#define LL long long
using namespace std;
class DSU {
int Set[MAXN];
public:
void init(int n) {for(int i=0; i<=n; i++) {Set[i]=i;};}
int Find(int x) {return(Set[x] == x ? x : Set[x] = Find(Set[x]));}
void Union(int x, int y) {Set[Find(x)] = Find(y);}
} UF;
multiset<pair<pair<int,int> , bool> > R; // [[val, id], s = true, t = false]
bool active[MAXN];
LL plan_roller_coaster(vector<int> s, vector<int> t) {
int N = (int) s.size();
LL ans = 0;
UF.init(N);
for (int i=0; i < N; i++) {
R.insert({{s[i],i}, true});
R.insert({{t[i],i}, false});
}
R.insert({{0, N}, false});
R.insert({{1<<30, N}, true});
int up=0, down=0;
for (auto p: R) {
if (!active[p.first.second]) {
if (p.second) {up++;}
else {down++;}
active[p.first.second] = true;
} else {
if (p.second) {down--;}
else {up--;}
active[p.first.second] = false;
}
if (down > up && p != *R.rbegin()) {
//printf("Link up %d %d\n", p.first.first,(*R.upper_bound(p)).first.first);
UF.Union(p.first.second, (*R.upper_bound(p)).first.second);
} else if (up > down) {
assert(p != *R.rbegin());
//printf("Link down %d %d\n", p.first.first,(*R.upper_bound(p)).first.first);
ans += ((LL) (*R.upper_bound(p)).first.first - p.first.first)*((LL) up - down);
UF.Union(p.first.second, (*R.upper_bound(p)).first.second);
}
}
//printf("%d\n", ans);
vector<pair<int, pair<int,int> > > Edge;
int prev_id, prev_pos;
for (auto p: R) {
if (p == *R.begin()) {
prev_id = p.first.second, prev_pos = p.first.first;
continue;
} else {
Edge.push_back({p.first.first - prev_pos, {p.first.second, prev_id}});
prev_id = p.first.second, prev_pos = p.first.first;
}
}
sort(Edge.begin(), Edge.end());
for (auto e: Edge) {
if (UF.Find(e.second.first) != UF.Find(e.second.second)) {
UF.Union(e.second.first, e.second.second);
ans += e.first;
}
}
return(ans);
}
