#include <bits/stdc++.h>
#include "teams.h"
#define pb push_back
#define pii pair<int, int>
#define pb push_back
using namespace std;
typedef long long ll;
const int maxN = 1e5 + 10, LOG = 19;
vector <int> qu[maxN], lefts;
int cnt[maxN], n, lf[maxN], rg[maxN];
int seg[LOG][maxN], perm[maxN];
bool cmp(int i, int j)
{
return make_pair(lf[i], rg[i]) < make_pair(lf[j], rg[j]);
}
void build(int lg = 0, int s = 0, int e = n)
{
if(e - s < 2)
{
int p = perm[s];
seg[lg][s] = rg[p];
return ;
}
int mid = (s + e)/2;
build(lg + 1, s, mid);
build(lg + 1, mid, e);
merge(seg[lg + 1] + s, seg[lg + 1] + mid, seg[lg + 1] + mid, seg[lg + 1] + e, seg[lg] + s);
return ;
}
int get(int lg, int L, int R, int ql, int qr, int s = 0, int e = n)
{
if(L<=s && e<=R)
{
int idl = lower_bound(seg[lg] + s, seg[lg] + e, ql) - seg[lg];
int idr = upper_bound(seg[lg] + s, seg[lg] + e, qr) - seg[lg];
return idr - idl;
}
if(L>=e || s>=R) return 0;
int mid = (s + e)/2;
return get(lg + 1, L, R, ql, qr, s, mid) + get(lg + 1, L, R, ql, qr, mid, e);
}
void init(int N, int A[], int B[]) {
n = N;
for (int i=0; i<n; i++) lf[i] = A[i], rg[i] = B[i], lefts.pb(lf[i]);
sort(lefts.begin(), lefts.end());
for (int i=0; i<n; i++) perm[i] = i;
sort(perm, perm + n, cmp);
build();
}
vector <int> vc;
int can(int m, int k[]) {
//for (auto x : lefts) cout << x << ' '; cout << endl;
vc.clear();
for (int i=0; i<m; i++) vc.pb(k[i]), cnt[k[i]] ++;
sort(vc.begin(), vc.end());
vc.resize(unique(vc.begin(), vc.end()) - vc.begin());
int sz = (int) vc.size(), last = 0;
ll s = 0, p = 0;
for (int i=0; i<sz; i++)
{
int x = vc[i];
int pl = upper_bound(lefts.begin(), lefts.end(), last) - lefts.begin();
int pr = lower_bound(lefts.begin(), lefts.end(), x + 1) - lefts.begin();
int g1 = get(0, pl, pr, x , n);
pl = 0;
pr = lower_bound(lefts.begin(), lefts.end(), last + 1) - lefts.begin();
int g2 = get(0, pl, pr, last, x - 1);
if(p >= g2) p -= g2;
else s -= g2 - p, p = 0;
s += g1;
if(s < 1LL * cnt[x] * x) {
for (int j=0; j<m; j++) cnt[k[j]] --;
return 0;
}
s -= 1LL * cnt[x] * x;
p += 1LL * cnt[x] * x;
last = vc[i];
//cout << i << " --> " << s << ',' << p << endl;
//cout << cnt[i] << endl;
}
for (int i=0; i<m; i++) cnt[k[i]] --;
return 1;
}
