#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(), x.end()
#define ln '\n'
struct Dsu{
vector <int> fa;
Dsu(int n){
fa.resize(n);
iota(all(fa), 0);
}
int get(int x){
return x ^ fa[x] ? fa[x] = get(fa[x]) : x;
}
bool merge(int u, int v){
u = get(u), v = get(v);
if ( u == v ) return false;
fa[v] = u;
return true;
}
};
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
int n = s.size(), m;
s.pb(2e9), t.pb(1);
{ // compression
vector <int> p_;
for ( int i = 0; i <= n; i++ ){
p_.pb(s[i]); p_.pb(t[i]);
}
sort(all(p_));
p_.resize(unique(all(p_)) - p_.begin());
m = p_.size();
for ( int i = 0; i <= n; i++ ){
s[i] = lower_bound(all(p_), s[i]) - p_.begin();
t[i] = lower_bound(all(p_), t[i]) - p_.begin();
}
}
vector <int> pf(m);
for ( int i = 0; i <= n; i++ ){
pf[t[i]]--;
pf[s[i]]++;
}
for ( int i = 1; i < m; i++ ){
pf[i] += pf[i - 1];
}
Dsu ds(m);
for ( int i = 0; i <= n; i++ ){
ds.merge(s[i], t[i]);
}
for ( int i = 0; i + 1 < m; i++ ){
if ( pf[i] > 0 ){
return 1;
}
if ( pf[i] < 0 ) ds.merge(i, i + 1);
}
int root = ds.get(0);
for ( int i = 0; i < m; i++ ){
if ( ds.get(i) != root ){
return 1;
}
}
return 0;
}
