#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int maxn = 4e5+10;
struct DSU {
int pai[maxn], peso[maxn];
DSU() { for(int i = 0; i < maxn; i++) pai[i] = i, peso[i] = 1; }
int find(int x) { return pai[x] == x ? x : pai[x] = find(pai[x]); }
void join(int a, int b) {
a = find(a), b = find(b);
if(a == b) return;
if(peso[a] < peso[b])
swap(a, b);
pai[b] = a;
peso[a] += peso[b];
}
} dsu;
map<int,int> qtd;
struct Itv { int l, r; bool operator<(const Itv& o) { return r-l > o.r-o.l; } };
vector<Itv> itv;
long long plan_roller_coaster(vector<int> s, vector<int> t) {
int n = (int) s.size(), ans = 0;
for(int i = 0; i < n; i++) {
qtd[s[i]]++, qtd[t[i]]--;
itv.push_back({min(s[i], t[i]), max(s[i], t[i])});
}
for(auto it = qtd.begin(); it != qtd.end(); ++it) {
if(it != qtd.begin())
it->second += prev(it)->second;
if(it->second != 1 && next(it) != qtd.end()) {
itv.push_back({it->first, next(it)->first});
if(it->second > 1)
ans += (it->second-1) * (next(it)->first - it->first);
}
}
// SUBTASK 3 <---------------------------------------------------------------------------------------------------------------->
if(ans) return ans; // se eu tive q colocar alguma aresta pra trás então não da pra fazer com 0
// agora que eu tenho todos os intervalos, tenho que checar as intersecções
sort(itv.begin(), itv.end()); // ordeno pelo de maior tamanho
map<int,int> compress;
for(auto [l, r] : itv)
compress[l] = 0, compress[r] = 0;
int coord = 0;
for(auto& it : compress)
it.second = ++coord;
vector<int> pai(maxn), vis(maxn); iota(pai.begin(), pai.end(), 1); // todo mundo começa apontando pro próximo
for(auto [l, r] : itv) {
l = compress[l], r = compress[r];
vis[l] = 1, vis[r] = 1;
while(l < r) {
if(vis[l])
dsu.join(l, r);
int nxt = pai[l];
pai[l] = r;
l = nxt;
}
}
int comp = dsu.find(compress[itv[0].l]);
for(auto [l, r] : itv)
if(dsu.find(compress[l]) != comp) return 1; // pra subtask q só quer saber se dá com zero bastar printar 1
// se não deu ruim no for acima então todo mundo está ligado na mesma componente e dá pra fazer 0
return 0;
}
