#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
typedef int INT;
#define FOR(i,l,r) for(int i = (l); i < (r); i++)
#define fst first
#define snd second
#define pb push_back
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
struct segtree{
vvi t;
segtree(int n){
t.resize(4*n);
}
void build(vi &arr, int lb, int rb, int n){
if(rb-lb == 1) {
t[n].pb(arr[lb]);
return;
}
int mb = (lb+rb)/2;
build(arr, lb, mb, n<<1);
build(arr, mb, rb, n<<1|1);
sort(&arr[lb], &arr[rb]);
FOR(i, lb, rb) t[n].pb(arr[i]);
}
int qu(int l, int r, int c, int lb, int rb, int n){
if(l == r) return 0;
if(n!=0){
//cout<<n<<endl;
//cout << l << " " << r << endl;
}
if(l <= lb and rb <= r) return upper_bound(t[n].begin(), t[n].end(), c) - t[n].begin();
int mb = (lb+rb)/2;
int s = 0;
if(l < mb) s += qu(l, r, c, lb, mb, n<<1);
if(r > mb) s += qu(l, r, c, mb, rb, n<<1|1);
return s;
}
};
segtree t(0);
vii a, pre;
vi arr, prefix;
vi A, B;
int N;
void init(INT n, INT x[], INT y[]) {
N = n;
FOR(i, 0, N) A.pb(x[i]), B.pb(y[i]);
t = segtree(N);
a.resize(N);
FOR(i, 0, N) a[i] = {B[i], A[i]};
sort(a.begin(), a.end());
arr.resize(N);
FOR(i, 0, N) arr[i] = a[i].snd;
t.build(arr, 0, N, 1);
FOR(i, 0, N) pre.pb({A[i], -1});
FOR(i, 0, N) pre.pb({B[i], 1});
sort(pre.begin(), pre.end());
prefix.resize(2*N, 0);
FOR(i, 1, 2*N) prefix[i] = prefix[i-1] - pre[i-1].snd;
}
INT can(INT M, INT K[]) {
int T = upper_bound(pre.begin(), pre.end(), make_pair(K[0], 0)) - pre.begin();
int active = prefix[T], tbc = 0;
FOR(i, 0, M-1){
//cout << active << " " << tbc << endl;
if(active < K[i]) return 0;
active -= K[i];
tbc += K[i];
if(K[i] == K[i+1]) continue;
int nT = upper_bound(pre.begin(), pre.end(), make_pair(K[i+1], 0)) - pre.begin();
int l = lower_bound(a.begin(), a.end(), make_pair(K[i], 0)) - a.begin();
int r = lower_bound(a.begin(), a.end(), make_pair(K[i+1], 0)) - a.begin();
tbc -= t.qu(l, r, K[i], 0, N, 1);
active = prefix[nT] - tbc;
}
if(active < K[M-1]) return 0;
return 1;
}
