#include <bits/stdc++.h>
#include "railroad.h"
template <class T>
using Vec = std::vector<T>;
using ll = long long;
constexpr int MAX = 1000000000;
struct DSU {
Vec<int> par;
DSU(const int n): par(n, -1) { }
int find(const int u) {
return par[u] < 0 ? u : par[u] = find(par[u]);
}
void merge(int u, int v) {
u = find(u);
v = find(v);
if (u == v) {
return;
}
if (par[u] > par[v]) {
std::swap(u, v);
}
par[u] += par[v];
par[v] = u;
}
};
ll plan_roller_coaster(Vec<int> s, Vec<int> t) {
s.push_back(MAX);
t.push_back(1);
const int n = (int) s.size();
Vec<int> cmp;
cmp.reserve(2 * n);
std::copy(s.cbegin(), s.cend(), std::back_inserter(cmp));
std::copy(t.cbegin(), t.cend(), std::back_inserter(cmp));
std::sort(cmp.begin(), cmp.end());
cmp.erase(std::unique(cmp.begin(), cmp.end()), cmp.end());
for (auto &x: s) {
x = std::lower_bound(cmp.begin(), cmp.end(), x) - cmp.begin();
}
for (auto &x: t) {
x = std::lower_bound(cmp.begin(), cmp.end(), x) - cmp.begin();
}
const int len = (int) cmp.size();
Vec<int> coeff(len);
for (const auto x: s) {
coeff[x] -= 1;
}
for (const auto x: t) {
coeff[x] += 1;
}
Vec<int> edge(len);
DSU dsu(len);
for (int i = 0; i < len; ++i) {
edge[i] = (i == 0 ? 0 : edge[i - 1] + coeff[i]);
if (edge[i] < 0) {
return 1;
}
if (i + 1 == len && edge[i] > 0) {
return 1;
}
if (edge[i] > 0) {
dsu.merge(i, i + 1);
}
}
for (int i = 0; i < n; ++i) {
dsu.merge(s[i], t[i]);
}
for (int i = 0; i < n; ++i) {
if (dsu.find(s[0]) != dsu.find(s[i])) {
return 1;
}
if (dsu.find(s[0]) != dsu.find(t[i])) {
return 1;
}
}
return 0;
}
