#include "teams.h"
#include <bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
typedef pair<int, int> pii;
const int N = 5e5 + 10;
const int Sq = 1000;
int n, L[N], R[N], mk[N];
struct Block {
int l, r, lazy;
vector<int> ord, tmp;
bool Marked;
void Build(int _l, int _r){
l = _l; r = _r; lazy = 0; Marked = false;
ord.resize(r - l);
iota(all(ord), l);
sort(all(ord), [&](int i, int j){
return L[i] < L[j];
});
}
void Rebuild(){
tmp.clear();
for(auto x : ord){
if(!mk[x])
tmp.pb(x);
}
ord.clear();
for(auto x : tmp)
ord.pb(x);
}
void Relax(){
if(!lazy) return ;
Marked = true;
for(int i = 0; i < lazy; i++) mk[ord[i]] = 1;
lazy = 0;
Rebuild();
}
int Count(int x){
int Lb = -1, Rb = ord.size();
int mid;
while(Lb + 1 < Rb){
mid = (Lb + Rb) >> 1;
if(L[ord[mid]] <= x) Lb = mid;
else Rb = mid;
}
return Rb - lazy;
}
void Pick(int cnt){
lazy += cnt;
}
int Solve(int cnt, int sz){
Relax();
for(int i = l; i < r; i++){
if(!mk[i] && L[i] <= sz && sz <= R[i]){
cnt --;
mk[i] = 1;
Marked = true;
if(cnt == 0) break;
}
}
Rebuild();
return cnt;
}
void Reset(){
lazy = 0;
if(!Marked) return ;
Marked = false;
for(int i = l; i < r; i++) mk[i] = 0;
Rebuild();
}
};
Block bl[Sq];
int k;
void init(int _n, int A[], int B[]) {
n = _n;
vector<int> I(n);
iota(all(I), 0);
sort(all(I), [&](int i, int j){
if(B[i] != B[j]) return B[i] < B[j];
return A[i] < A[j];
});
for(int i = 0; i < n; i++) L[i] = A[I[i]];
for(int i = 0; i < n; i++) R[i] = B[I[i]];
k = 0;
for(int i = 0; i < n; i += Sq){
bl[i / Sq].Build(i, min(i + Sq, n));
k ++;
}
}
int can(int m, int K[]){
for(int i = 0; i < k; i++) bl[i].Reset();
int sz, req, res;
for(int gp = 0; gp < m; gp++){
sz = K[gp];
req = sz;
for(int i = 0; i < k; i++){
if(req == 0) break;
if(R[bl[i].r - 1] < sz) continue;
if(R[bl[i].l] < sz){
req = bl[i].Solve(req, sz);
continue;
}
res = bl[i].Count(sz);
if(res <= req){
req -= res;
bl[i].Pick(res);
} else {
req = bl[i].Solve(req, sz);
assert(req == 0);
}
}
if(req)
return 0;
}
return 1;
}
