#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int MAXN = 5e5+5;
pii students[MAXN];
int n;
class stree {
public:
int sum = 0;
stree *l = nullptr;
stree *r = nullptr;
stree(int lp, int rp) {
if (lp < rp) {
int mid = (lp+rp)/2;
l = new stree(lp, mid);
r = new stree(mid+1, rp);
}
}
stree(stree *prv) {
sum = prv->sum+1;
}
stree(stree *l, stree *r) : l(l), r(r) {
sum = l->sum + r->sum;
}
stree *upd(int p, int lp = 0, int rp = n-1) {
if (lp > p || rp < p) return this;
if (lp == rp) {
return new stree(this);
}
int mid = (lp+rp)/2;
return new stree(l->upd(p, lp, mid), r->upd(p, mid+1, rp));
}
int query(int lv, int rv, int lp = 0, int rp = n-1) {
if (lp > rv || rp < lv) return 0;
if (lp >= lv && rp <= rv) return sum;
int mid = (lp+rp)/2;
return l->query(lv, rv, lp, mid)+r->query(lv, rv, mid+1, rp);
}
};
stree *trees[MAXN];
void init(int N, int A[], int B[]) {
n = N;
for (int i = 0; i < n; i++) {
students[i] = pii(A[i]-1, B[i]-1);
}
sort(students, students+n);
trees[0] = new stree(0, n-1);
int j = 0;
for (int i = 0; i < n; i++) {
trees[i+1] = trees[i];
while (j < n && students[j].first == i) trees[i+1] = trees[i+1]->upd(students[j++].second);
}
}
int sum(int x0, int x1, int y0, int y1) {
return trees[x1+1]->query(y0, y1)-trees[x0]->query(y0, y1);
}
int can(int m, int k[]) {
sort(k, k+m);
for (int i = 0; i < m; i++) k[i]--;
int sub = 0;
for (int i = 0; i < m; i++) {
int p = i ? k[i-1] : -1;
int amt = k[i]+1;
amt -= sum(p+1, k[i], k[i], k[i+1]-1);
int lft = sum(0, p, k[i], k[i+1]-1);
int v = min(sub, lft);
lft -= v;
sub -= v;
amt -= lft;
if (amt <= 0) continue;
int above = sum(0, k[i], k[i+1], n-1)-sub;
assert(above >= 0);
if (above < amt) return 0;
sub += amt;
}
return 1;
}
