/* AM+DG */
/*
For subtask 3, consider, for each rail, the prefix it can reach
4 2 1 0 -> doesn't work
3 1 1 1
4 2 2 0 -> works
3 2 1 1
4 3 1 0 -> works
4 2 1 1 -> doesn't work
2 2 4 0 -> doesn't work
The cost of a placement is.. hmm
max(t[i] - s[i + 1], 0) + max(t[i - 1] - s[i], 0) -> if separated more than two apart
t[i] t[i + 1] t[i + 2] t[i + 3]
s[i] s[i + 1] s[i + 2] s[i + 3]
c = max(t[i] - s[i + 1], 0) + max(t[i + 1] - s[i + 2], 0) + max(t[i + 2] - s[i + 3], 0)
c' = max(t[i] - s[i + 2], 0) + max(t[i + 2] - s[i + 1], 0) + max(t[i + 1] - s[i + 3], 0)
4
NULL -> 5
1 7 -> 1
4 3 -> 4
5 8 -> 1
6 6 -> 2
INF -> 0
s[i] t[i]
s[j] t[j]
max(t[i] - s[j], 0)
s[i] t[i] s[j] t[j] -> 0
s[i] t[i] t[j] s[j] -> 0
s[i] s[j] t[i] t[j] -> t[i] - s[j]
s[i] s[j] t[j] t[i] ->
s[i] t[j] t[i] s[j]
s[i] t[j] s[j] t[i]
t[i] s[i] s[j] t[j]
t[i] s[i] t[j] s[j]
s[j] s[i] t[i] t[j]
s[j] s[i] t[j] t[i]
t[j] s[i] t[i] s[j]
t[j] s[i] s[j] t[i]
t[i] s[j] s[i] t[j]
t[i] t[j] s[i] s[j]
s[j] t[i] s[i] t[j]
s[j] t[j] s[i] t[i]
t[j] t[i] s[i] s[j]
t[j] s[j] s[i] t[i]
t[i] s[j] t[j] s[i]
t[i] t[j] s[j] s[i]
s[j] t[i] t[j] s[i]
s[j] t[j] t[i] s[i]
t[j] t[i] s[j] s[i]
t[j] s[j] t[i] s[i]
possible to do with 0:
is there a permutation of s and t s.t t[i] <= s[i + 1]
1 5 4 3 1 6
0 -> 0
1 -> 0, 1, 2, 3, 4
2 -> 0, 1, 2, 3
3 -> 0, 1, 2
4 -> 0
5 -> 0, 1, 2, 3, 4, 5, 6
0 -> 0
1 -> 0, 1, 2
2 -> 0, 1, 2
3 -> 0, 1, 2, 3
4 -> 0
5 -> 0, 1, 2, 3, 4, 5, 6
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)
class UF {
public:
vi par;
vi csize;
int n;
int comps;
UF(int a_n): n(a_n), par(a_n, 0), csize(a_n, 1), comps(a_n) {
LI(i, 0, n) {
par[i] = i;
}
}
int find(int i) {
while(i != par[i]) {
par[i] = par[par[i]];
i = par[i];
}
return i;
}
bool conn(int i, int j) {
return find(i) == find(j);
}
void unify(int i, int j) {
int pi = find(i), pj = find(j);
if(pi == pj) return;
int& is = csize[pi];
int& js = csize[pj];
if(is < js) {
par[pi] = pj; // ! Careful, you set this to par[i] = j, are you fine???
js += is;
} else {
par[pj] = pi;
is += js;
}
comps--;
#ifdef DEBUG
cout << "NCOMPS: " << comps << " " << pi << " " << pj << endl;
#endif
}
};
ll plan_roller_coaster(vi s, vi t) {
s.push_back(INF(int));
t.push_back(0);
ll n = s.size();
vpi pts;
// Creating a list of entry and exit points
LI(i, 0, n) {
pts.push_back({s[i], 1});
pts.push_back({t[i], -1});
}
sort(pts.begin(), pts.end());
// Make a UFDS here
UF uf((n) << 1);
int cur_depth = 0;
ll ans = 0ll;
LI(i, 0, ((n) << 1) - 1) {
auto [ccoord, change] = pts[i];
auto ncoord = pts[i + 1].fi;
#ifdef DEBUG
cout << "POINT " << i + 1 << ": " << ncoord << endl;
#endif
cur_depth += change;
if(ccoord != ncoord) {
// The next coordinate is different! Process the current coordinate
if(cur_depth >= 1) {
ans += (ll)(cur_depth) * (ll)(ncoord - ccoord);
}
// If may connector rail, unify the components, haha
if(cur_depth != 0) {
uf.unify(i, i + 1);
}
} else {
uf.unify(i, i + 1);
}
// Otherwise, nothing much to do here, carry on with your jinsei, hito-san! :D
}
vector<pair<int, pi>> e;
#ifdef DEBUG
cout << "BASE ANS: " << ans << endl;
#endif
// Unify vertices pointed by railroads
LI(i, 0, (n) << 1) {
int v1 = s[i], v2 = t[i];
int l1, r1;
int l = -1, r = (n) << 1;
while(r - l > 1) {
int m = (l + r) >> 1;
if(v1 <= pts[m].fi) r = m;
else l = m;
}
l1 = r;
l = -1; r = (n) << 1;
while(r - l > 1) {
int m = (l + r) >> 1;
if(v2 <= pts[m].fi) r = m;
else l = m;
}
r1 = r;
uf.unify(l1, r1);
}
LI(i, 0, ((n) << 1) - 1) {
if(!uf.conn(i, i + 1)) {
e.push_back({pts[i + 1].fi - pts[i].fi, {uf.find(i), uf.find(i + 1)}});
#ifdef DEBUG
cout << pts[i + 1].fi - pts[i].fi << " " << uf.find(i) << " " << uf.find(i + 1) << endl;
#endif
}
#ifdef DEBUG
// cout << pts[i].fi << " " << uf.find(i) << endl;
#endif
}
sort(e.begin(), e.end());
// Kruskal's Time wahoo!! :D
int cur_e_ind = 0;
while(uf.comps > 1) {
auto [weight, vertices] = e[cur_e_ind];
auto [i, j] = vertices;
if(!uf.conn(i, j)) {
uf.unify(i, j);
ans += (ll)weight;
#ifdef DEBUG
cout << "Added " << weight << endl;
#endif
}
cur_e_ind++;
}
return ans;
}
#ifdef DEBUG
int main() {
int n;
cin >> n;
vi s(n, 0);
vi t(n, 0);
LI(i, 0, n) {
cin >> s[i] >> t[i];
}
cout << plan_roller_coaster(s, t) << endl;
}
#endif
