#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;
typedef pair<double, int> pt;
vector<p2> pts;
node* roots[int(1e5)];
void init(int N, int A[], int B[])
{
n = N;
vi a(n);
vi b(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);
}
struct tnode
{
p2 corner;
int value, sum=0, prio;
tnode *l=0, *r=0;
tnode(p2 corner, int sum) : corner(corner), prio(rand()), value(value) {}
};
typedef tnode* pnode;
int get_sum(pnode x) { return x ? x->sum : 0; }
void pull(pnode x)
{
if (!x) return;
x->sum = get_sum(x->l) + get_sum(x->r) + x->value;
}
void split(pnode x, pnode& l, pnode& r, int s)
{
if (!x) return void(l = r = 0);
if (x->corner.first <= s)
split(x->l, l, x->l, s), r = x;
else
split(x->r, x->r, r, s), l = x;
pull(x);
}
void merge(pnode& x, pnode l, pnode r)
{
if (!l || !r)
x = l ? l : r;
else if (l->prio < r->prio)
merge(r->l, l, r->l), x = r;
else
merge(l->r, l->r, r), x = l;
pull(x);
}
int sum(vector<p2>& hull, int xhi, int ylo, int yhi)
{
int prev = -1;
int taken = 0;
int lo = -1;
int hi = sz(hull);
while (lo + 1 < hi)
{
int mid = (lo + hi) / 2;
if (hull[mid].second <= yhi)
{
hi = mid;
}
else lo = mid;
}
if (hi > 0) prev = hull[hi - 1].first;
repp(i, hi, sz(hull))
{
p2 p = hull[i];
taken += rectangle_sum(prev + 1, p.first, p.second);
prev = p.first;
}
if (hi > 0 && sz(hull))
{
taken += rectangle_sum(0, hull[hi-1].first, yhi);
}
return rectangle_sum(0, xhi, yhi) - taken;
}
bool dominates(p2 a, p2 b)
{
return a.first >= b.first && a.second >= b.second;
}
const int inf = int(2e9);
p2 invalid = p2(-inf, -inf);
p2 lower_bound(pnode root, int x)
{
if (!root) return invalid;
if (root->corner.first >= x)
{
p2 left_result = lower_bound(root->l, x);
if (left_result != invalid) return left_result;
else return root->corner;
}
else
{
return lower_bound(root->r, x);
}
}
p2 rev_bound(pnode root, int x)
{
if (!root) return invalid;
p2 result = invalid;
if (root->corner.first <= x) {
result = root->corner;
p2 right_result = rev_bound(root->r, x);
if (right_result != invalid) result = right_result;
}
else result = rev_bound(root->l, x);
return result;
}
int can(int m, int K[]) {
vi k(m);
rep(i, m) k[i] = K[i];
sort(all(k));
pnode hull = 0;
vector<p2> taken_hull;
auto insert = [&](p2 new_corner)
{
bool good = 1;
repe(p, taken_hull) if (dominates(p, new_corner)) good = 0;
p2 lo = lower_bound(hull, new_corner.first);
if ((new_corner.first <= lo.first && new_corner.second <= lo.second))
{
assert(!good);
}
else
{
while (1)
{
p2 p = rev_bound(hull, new_corner.first);
if (p == invalid) break;
assert(p.first <= new_corner.first);
if (p.second <= new_corner.second)
{
pnode l, mid, r;
split(hull, l, r, p.first);
split(hull, l, mid, p.first - 1);
merge(hull, l, r);
}
else break;
}
}
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);
}
assert(sz(taken_hull) <= 3);
sort(all(taken_hull));
};
int lo = 0;
rep(i, m)
{
while (lo < sz(pts) && pts[lo].second < k[i])
{
insert(p2(k[i], 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;
}
