#include "teams.h"
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#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 = 500;
int n, L[N], R[N], mk[N];
struct Block {
int l, r, lazy;
int ord[Sq], sz_ord;
int lord[Sq], sz_lord;
//vector<int> ord, lord;
bool Marked;
void Build(int _l, int _r){
l = _l; r = _r; lazy = 0; Marked = false;
sz_ord = r - l; sz_lord = r - l;
//ord.resize(r - l);
iota(ord, ord + sz_ord, l);
sort(ord, ord + sz_ord, [&](int i, int j){
return L[i] < L[j];
});
for(int i = 0; i < sz_ord; i++)
lord[i] = ord[i];
}
inline void Rebuild(){
//ord.clear();
sz_ord = 0;
for(int i = 0; i < sz_lord; i++){
if(!mk[lord[i]])
ord[sz_ord ++] = lord[i];
}
}
inline void Relax(){
if(!lazy) return ;
Marked = true;
for(int i = 0; i < lazy; i++) mk[ord[i]] = 1;
lazy = 0;
//Rebuild();
}
inline int Count(int x, int up){
if(lazy - 1 + up < sz_ord && L[ord[lazy - 1 + up]] <= x) return up;
int Lb = lazy - 1, Rb = sz_ord;
int mid;
while(Lb + 1 < Rb){
mid = (Lb + Rb) >> 1;
if(L[ord[mid]] <= x) Lb = mid;
else Rb = mid;
}
return Rb - lazy;
}
inline void Pick(int cnt){
lazy += cnt;
}
inline 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;
}
inline void Reset(){
lazy = 0;
if(!Marked) return ;
Marked = false;
for(int i = l; i < r; i++) mk[i] = 0;
sz_ord = r - l;
for(int i = 0; i < r - l; i++)
ord[i] = lord[i];
//Rebuild();
}
};
Block bl[N / Sq + 10];
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[]){
sort(K, K + m);
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;
while(gp + 1 < m && K[gp + 1] == sz){
req += sz;
gp ++;
}
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, req + 1);
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;
}
