#include "teams.h"
#include <vector>
#include <cassert>
#include <algorithm>
#include <iostream>
using namespace std;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define index(x, y) (int)(lower_bound(all(x), y)-x.begin())
#define pb push_back
const int MAX_N = 5e5+10;
struct Node {
int val;
Node *left, *right;
Node() : val(0), left(NULL), right(NULL) {}
};
int query(Node *n, int a, int b, int l=0, int r=MAX_N) {
if (b <= l || r <= a) return 0;
if (a <= l && r <= b) return n->val;
int ret = 0;
if (n->left) ret += query(n->left, a, b, l, (l+r)/2);
if (n->right) ret += query(n->right, a, b, (l+r)/2, r);
return ret;
}
Node *add(Node *n, int x, int l=0, int r=MAX_N) {
if (r-l == 1) {
Node *ret = new Node();
ret->val = n->val+1;
return ret;
}
if (n->left == NULL) n->left = new Node();
if (n->right == NULL) n->right = new Node();
Node *ret = new Node();
if (x < (l+r)/2) {
ret->left = add(n->left, x, l, (l+r)/2);
ret->right = n->right;
}
else {
ret->left = n->left;
ret->right = add(n->right, x, (l+r)/2, r);
}
ret->val = n->val+1;
return ret;
}
int N;
vector<int> G[500010];
Node *seg[500010];
inline int count(int l, int a, int b) { return query(seg[l], a, b+1); }
void init(int NN, int A[], int B[]) {
N = NN;
rep(i, N) G[A[i]].pb(B[i]);
seg[0] = new Node();
for (int i=1; i<=N; i++) {
seg[i] = seg[i-1];
for (int r : G[i]) seg[i] = add(seg[i], r);
}
}
int C[MAX_N], demand[MAX_N], used[MAX_N];
int can(int MM, int K[]) {
long long sum = 0;
rep(i, MM) sum += K[i];
if (sum > N) return 0;
sort(K, K+MM);
vector<int> xs;
rep(i, MM) C[i] = demand[i] = used[i] = 0;
rep(i, MM) {
if (xs.empty() || xs.back() != K[i]) xs.pb(K[i]);
demand[xs.size()-1] += K[i];
}
int M = xs.size();
rep(k, M) {
int d = demand[k];
for (int r=k; r<M; r++) {
int rpos = r+1==xs.size()?N:(xs[r+1]-1);
int e = min(count(xs[k], xs[r], rpos)-used[r], d);
d -= e;
used[r] += e;
if (d == 0) break;
}
if (d > 0) return 0;
}
return 1;
}
