// Oh damn! Suddenly you're free to fly...
#include<bits/stdc++.h>
#include "teams.h"
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 5e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;
pii p[maxn];
int n;
vector<pii> vec[4 * maxn];
vector<int> LC[4 * maxn], RC[4 * maxn];
bool leaf[4 * maxn];
int used[4 * maxn];
int CNT_LEAFS;
void shift(int l, int r, int id){
if(leaf[id] == 0)
return;
assert(r-l > 1);
leaf[id] = 0;
// used[id] = 0;
leaf[2*id] = leaf[2*id+1] = 1;
used[2*id] = LC[id][ used[id] ];
used[2*id + 1] = RC[id][ used[id] ];
CNT_LEAFS++;
}
void build(int l = 0, int r = n, int id = 1){
if(r-l == 1){
vec[id].PB(p[l]);
LC[id].PB(-1), RC[id].PB(-1);
return; // behold LC RC
}
int mid = (l+r) >> 1;
build(l, mid, 2*id);
build(mid, r, 2*id + 1);
int pt1 = 0, pt2 = 0;
while(pt1 < sz(vec[2*id]) || pt2 < sz(vec[2*id+1])){
LC[id].PB(pt1), RC[id].PB(pt2);
if(pt2 == sz(vec[2*id+1]) || (pt1 != sz(vec[2*id]) && vec[2*id][pt1].S > vec[2*id+1][pt2].S))
vec[id].PB(vec[2*id][pt1++]);
else
vec[id].PB(vec[2*id+1][pt2++]);
}
LC[id].PB(pt1), RC[id].PB(pt2);
}
void go(int pos, int &need, int RP = -1, int l = 0, int r = n, int id = 1){
if(id == 1){
int f = -1, s = n;
while(s-f > 1){
int mid = (f + s) >> 1;
if(vec[id][mid].S >= pos)
f = mid;
else
s = mid;
}
if(s - used[id] < need) //////
throw "SHIT";
RP = s;
}
if(need == 0 || RP - used[id] <= 0)
return;
if(p[l].F > pos)
return;
if(p[r-1].F <= pos && leaf[id] && RP - used[id] <= need){
need-= RP - used[id];
used[id] = RP;
return;
}
shift(l, r, id);
int mid = (l+r) >> 1;
go(pos, need, RC[id][RP], mid, r, 2*id+1);
go(pos, need, LC[id][RP], l, mid, 2*id);
}
void init(int n, int l[], int r[]){
for(int i = 0; i < n; i++)
p[i] = {l[i], r[i]};
sort(p, p + n);
::n = n;
build();
}
int can(int m, int a[]){
leaf[1] = 1;
used[1] = 0;
sort(a, a + m);
int need = 0;
for(int i = m-1; i >= 0; i--){
need+= a[i];
if(need > n)
return 0;
if(i == 0 || a[i] != a[i-1]){
CNT_LEAFS = 0;
try{
go(a[i], need);
if(need != 0)
throw "SHIT2";
}
catch(...){
return 0;
}
assert(CNT_LEAFS <= 37);
}
}
return 1;
}
