#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
const int N = 500005, L = 20;
struct ban
{
int l, r;
};
bool operator<(const ban& a, const ban& b)
{
return a.l < b.l;
}
int n;
ban a[N];
vector<int> v[N];
int root[N];
int z;
int t[N * L];
int ul[N * L], ur[N * L];
int ubd(int tl, int tr, int x, int pos)
{
int ypos = ++z;
ul[ypos] = ul[pos];
ur[ypos] = ur[pos];
t[ypos] = t[pos];
t[ypos]++;
if (tl == tr)
return ypos;
int m = (tl + tr) / 2;
if (x <= m)
{
ul[ypos] = ubd(tl, m, x, ul[pos]);
}
else
{
ur[ypos] = ubd(m + 1, tr, x, ur[pos]);
}
return ypos;
}
int qry(int tl, int tr, int l, int r, int pos)
{
if (l > r)
return 0;
if (tl == l && tr == r)
return t[pos];
int m = (tl + tr) / 2;
return (qry(tl, m, l, min(m, r), ul[pos]) +
qry(m + 1, tr, max(m + 1, l), r, ur[pos]));
}
int qryy(int l1, int r1, int l2, int r2)
{
return qry(1, n, l2, r2, root[r1]) - qry(1, n, l2, r2, root[l1 - 1]);
}
void init(int N_, int A[], int B[])
{
n = N_;
for (int i = 0; i < n; ++i)
{
a[i].l = A[i];
a[i].r = B[i];
v[a[i].l].push_back(a[i].r);
}
sort(a, a + n);
for (int i = 1; i <= n; ++i)
{
root[i] = root[i - 1];
for (int j = 0; j < sz(v[i]); ++j)
root[i] = ubd(1, n, v[i][j], root[i]);
}
}
int m;
int b[N];
int can(int M_, int K[])
{
m = M_;
for (int i = 0; i < m; ++i)
b[i] = K[i];
sort(b, b + m);
ll sum = 0;
for (int i = 0; i < m; ++i)
sum += b[i];
if (sum > n)
return 0;
/*multiset<int> s;
int j = 0;
for (int i = 0; i < m; ++i)
{
while (j < n && a[j].l <= b[i])
s.insert(a[j++].r);
while (!s.empty() && *s.begin() < b[i])
s.erase(s.begin());
if (sz(s) < b[i])
return 0;
for (int j = 0; j < b[i]; ++j)
s.erase(s.begin());
}*/
vector<pair<int, int> > v;
v.push_back(m_p(b[0], b[0]));
for (int i = 1; i < m; ++i)
{
if (b[i] == v.back().fi)
v.back().se += b[i];
else
v.push_back(m_p(b[i], b[i]));
}
vector<int> h;
h.assign(sz(v), 0);
for (int i = 0; i < sz(v); ++i)
{
for (int j = i; j < sz(v); ++j)
{
int nx;
if (j == sz(v) - 1)
nx = n + 1;
else
nx = v[j + 1].fi;
int q = qryy(1, v[i].fi, v[j].fi, nx - 1) - h[j];
if (q < v[i].se)
{
h[j] += q;
v[i].se -= q;
}
else
{
h[j] += v[i].se;
v[i].se = 0;
break;
}
}
if (v[i].se)
return 0;
}
return 1;
}
