#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll linf = ll(1e18);
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> p2;
#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define sz(container) ((int)container.size())
#define all(x) begin(x),end(x)
#if _LOCAL
#define assert(x) if (!(x)) __debugbreak()
#endif
struct node
{
node* lc=0, * rc=0;
int sum = 0;
node(node* lc, node* rc, int s) : lc(lc), rc(rc), sum(s) {}
};
node* build(int l, int r)
{
if (l==r)
{
return new node(0, 0, 0);
}
else
{
int mid = (l + r) / 2;
return new node(build(l, mid), build(mid + 1, r), 0);
}
}
node* update(node* x, int l, int r, int i, int s)
{
if (l==r)
{
return new node(0, 0, x->sum+s);
}
else
{
int mid = (l + r) / 2;
node* ret = new node(x->lc, x->rc, 0);
if (i <= mid) ret->lc = update(x->lc, l, mid, i, s);
else ret->rc = update(x->rc, mid + 1, r, i, s);
ret->sum = ret->lc->sum + ret->rc->sum;
return ret;
}
}
int query(node* x, int l, int r, int ql, int qr)
{
if (l > qr || r < ql) return 0;
if (l >= ql && r <= qr) return x->sum;
int mid = (l + r) / 2;
return query(x->lc, l, mid, ql, qr) + query(x->rc, mid + 1, r, ql, qr);
}
int n;
vi a;
vi b;
typedef pair<double, int> pt;
vector<p2> pts;
node* roots[int(1e5)];
void init(int N, int A[], int B[])
{
n = N;
a.resize(N);
b.resize(N);
rep(i, N) a[i] = A[i], b[i] = B[i];
rep(i, n)
{
pts.emplace_back(a[i], b[i]);
}
sort(all(pts), [](p2 a, p2 b)
{
return a.second < b.second;
});
node* root = build(0, n - 1);
rep(i, n)
{
root = roots[i] = update(root, 0, n - 1, pts[i].first, 1);
}
}
int rectangle_sum(int xlo, int xhi, int yhi)
{
return query(roots[yhi], 0, n - 1, xlo, xhi);
int ret = 0;
rep(i, yhi+1)
{
ret += pts[i].first >= xlo && pts[i].first <= xhi;
}
assert(ret == query(roots[yhi], 0, n - 1, xlo, xhi));
return ret;
}
typedef tuple<int, int, int> p3;
int sum(vector<p2>& hull, int xhi, int ylo, int yhi)
{
int prev = -1;
int taken = 0;
repe(p, hull)
{
taken += rectangle_sum(prev + 1, min(p.first, xhi), min(p.second, yhi));
if (p.first >= xhi) break;
prev = p.first;
}
return rectangle_sum(0, xhi, yhi)-taken;
}
bool dominates(p2 a, p2 b)
{
return a.first >= b.first && a.second >= b.second;
}
int can_brute(int m, vi k)
{
sort(all(k));
priority_queue<p2> waiting;
rep(i, n)
{
waiting.emplace(-a[i], i);
}
priority_queue<int> active;
rep(i, m)
{
int s = k[i];
while (sz(waiting) && (-waiting.top().first) <= s)
{
p2 p = waiting.top();
waiting.pop();
active.emplace(-b[p.second]);
}
int j = 0;
while (j < s)
{
if (active.empty()) return 0;
if (-active.top() < s)
{
active.pop();
continue;
}
active.pop();
j++;
}
}
return 1;
}
const int inf = int(2e9);
int can(int m, int K[]) {
vi k(m);
rep(i, m) k[i] = K[i];
if (m*n<m*m)
{
return can_brute(m, k);
}
sort(all(k));
vector<p2> taken_hull;
auto insert = [&](p2 new_corner)
{
bool good = 1;
repe(p, taken_hull) if (dominates(p, new_corner)) good = 0;
if (good)
{
auto it = taken_hull.begin();
while (it != taken_hull.end())
{
if (dominates(new_corner, *it))
{
it = taken_hull.erase(it);
}
else it = next(it);
}
taken_hull.push_back(new_corner);
}
sort(all(taken_hull));
};
int lo = 0;
rep(i, m)
{
while (lo < sz(pts) && pts[lo].second < k[i])
{
insert(p2(inf, lo));
lo++;
}
if (sum(taken_hull, k[i], 0, n-1)<k[i])
{
return 0;
}
int lob = lo-1;
int hib = n;
while (lob+1<hib)
{
int mid = (lob + hib) / 2;
if (sum(taken_hull, k[i], lo, mid) < k[i])
{
lob = mid;
}
else hib = mid;
}
p2 new_corner = p2(k[i], hib);
insert(new_corner);
}
return 1;
}
