#include "railroad.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int maxn = 2e5 + 20;
int s[maxn] , t[maxn] , n , ind[maxn];
pair<int , int> mn[maxn * 4];
bool cmps(int a , int b)
{
return s[a] < s[b];
}
void build(int s = 0 , int e = n , int v = 1)
{
if(e - s < 2)
{
mn[v] = {t[s] , s};
return;
}
int m = (s + e) / 2;
build(s , m , 2 * v);
build(m , e , 2 * v + 1);
mn[v] = min(mn[2 * v] , mn[2 * v + 1]);
}
void rem(int p , int s = 0 , int e = n , int v = 1)
{
if(e - s < 2)
{
mn[v] = {2e9 , -1};
return;
}
int m = (s + e) / 2;
if(p < m)
rem(p , s , m , 2 * v);
else
rem(p , m , e , 2 * v + 1);
mn[v] = min(mn[2 * v] , mn[2 * v + 1]);
}
pair<int , int> get(int l , int r , int s = 0 , int e = n , int v = 1)
{
if(l <= s && e <= r)
return mn[v];
if(r <= s || e <= l)
return make_pair(2e9 , -1);
int m = (s + e) / 2;
return min(get(l , r , s , m , 2 * v) , get(l , r , m , e , 2 * v + 1));
}
long long plan_roller_coaster(vector<int> S, vector<int> T)
{
n = (int)S.size();
for(int i = 0; i < n; i++)
s[i] = S[i] , t[i] = T[i] , ind[i] = i;
sort(ind , ind + n , cmps);
for(int i = 0; i < n; i++)
s[i] = S[ind[i]] , t[i] = T[ind[i]];
build();
int val = 1;
for(int _ = 0; _ < n; _++)
{
int k = lower_bound(s , s + n , val) - s;
auto tmp = get(k , n);
k = tmp.second , val = tmp.first;
if(k < 0)
return 1;
rem(k);
}
return 0;
}
