// 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, SQ = 1000;
pii p[maxn];
int n;
vector<pii> vec[4 * maxn];
vector<int> vecId[4 * maxn];
vector<int> LC[4 * maxn], RC[4 * maxn];
bool leaf[4 * maxn];
int used[4 * maxn];
int lazyUsed[4 * maxn];
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] ];
lazyUsed[2*id] = used[2*id];
lazyUsed[2*id+1] = used[2*id+1];
}
void build(int l = 0, int r = n, int id = 1){
if(r-l == 1){
vec[id].PB(p[l]);
vecId[id].PB(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]), vecId[id].PB(vecId[2*id][pt1]), pt1++;
else
vec[id].PB(vec[2*id+1][pt2]), vecId[id].PB(vecId[2*id+1][pt2]), pt2++;
}
LC[id].PB(pt1), RC[id].PB(pt2);
}
bool bad[maxn];
vector<int> clearBad;
inline void isBad(int x){
if(bad[x])
return;
bad[x] = 1;
clearBad.PB(x);
}
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]){
int delta = min(need, RP - used[id]);
if(delta == RP - used[id]){
need-= delta;
used[id]+= delta;
lazyUsed[id] = used[id];
return;
}
}
if(r-l < SQ){
for(int i = 0; i < lazyUsed[id]; i++)
isBad(vecId[id][i]);
for(int i = r-1; need && i >= l; i--){
if(!bad[i] && p[i].F <= pos && pos <= p[i].S)
isBad(i), --need, used[id]++;
}
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[]){
for(int x : clearBad){
bad[x] = 0;
}
clearBad.clear();
leaf[1] = 1;
used[1] = 0;
lazyUsed[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]){
try{
go(a[i], need);
if(need != 0)
throw "SHIT2";
}
catch(...){
return 0;
}
}
}
return 1;
}
