#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
typedef long long ll;
typedef pair<int,int> pi;
const int large = 5e5+5;
vector<pi> bit[large]; //r, val
void binit(){
for(int i = 0; i < large; i++)
bit[i].push_back({-large,0});
}
void add(int pos, int r){
for(; pos < large; pos += pos&-pos)
bit[pos].push_back({r,bit[pos].back().s+1});
}
int sum(int pos, int fr){
int ans = 0;
for(; pos > 0; pos -= pos&-pos){
int l = 0, r = bit[pos].size();
while(r-l > 1){
int mid = (l+r)>>1;
if(bit[pos][mid].f <= fr)
l = mid;
else r = mid;
}
ans += bit[pos][l].s;
}
return ans;
}
int sum(int l1, int l2, int r1, int r2){ //finds from (l1, l2], (r1, r2]
return sum(l2,r2)-sum(l1,r2)-sum(l2,r1)+sum(l1, r1);
}
int valfnd(int node, int r1, int r2){
int x = prev(lower_bound(bit[node].begin(), bit[node].end(),make_pair(r2+1,-1)))->s;
int y = prev(lower_bound(bit[node].begin(), bit[node].end(),make_pair(r1+1, -1)))->s;
return x-y;
}
int binsearch(int l2, int r1, int r2, int val){
int x = valfnd(l2,r1,r2);
if(x < val) return binsearch(l2-(l2&-l2), r1,r2,val-x);
int dif = l2&-l2;
for(dif >>= 1; dif > 0; dif >>= 1){
x -= valfnd(l2-dif, r1, r2);
if(x < val){
val -= x; return binsearch(l2-dif, r1, r2, val);
}
}
return l2;
}
int n;
void init(int _n, int _a[], int _b[]){
//input stuff
n = _n; //a = _a; b = _b;
binit();
vector<pi> ranges(n); // r,l
for(int i = 0; i < n; i++){
ranges[i] = {_b[i], _a[i]};
}
sort(ranges.begin(), ranges.end()); //increasing r order
for(auto &p: ranges){
add(p.s,p.f);
}
}
int can(int m, int k[]){
//fix input
vector<int> k2;
vector<pair<pi, int>> hchange = {{{0,n+1},0}}; //{x,y}, add at place
for(int i = 0; i < m; i++) k2.push_back(k[i]);
sort(k2.begin(), k2.end(), greater<int>());
for(int i = 0; i < m; i++){
int rem = k2[i];
int rp = k2[i];
while(rem > 0 && !hchange.empty()){
//remove if protected region is no longer valid
if(hchange.back().f.f > k2[i]){
hchange.pop_back(); continue;
}
//find value of current protected region
int ctop = hchange.back().f.s-1, cleft = hchange.back().f.f, cadd = hchange.back().s;
int x = sum(cleft-1, rp, k2[i]-1, ctop)+cadd;
//Move on if current region has too little
if(rem > x){
rem -= x; rp = cleft-1;
hchange.pop_back(); continue;
}
//Current region has just enough
int boval = sum(cleft, rp, k2[i]-1, ctop);
if(rem > boval){
hchange.pop_back();
hchange.push_back({{cleft, k2[i]}, x-rem});
rem = 0; continue;
}
//binary search to find position
int l = binsearch(rp, k2[i]-1, ctop, rem);
x = sum(l-1, rp, k2[i]-1, ctop);
hchange.push_back({{l,k2[i]}, x-rem});
rem = 0;
continue;
}
if(rem > 0) return 0;
}
return 1;
}
