#include "teams.h"
#include <bits/stdc++.h>
#define maxn 500005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;
int n;
int a[maxn], b[maxn];
struct node {
int val = 0;
node *left_child = nullptr, *right_child = nullptr;
node() {}
node(int _val) : val(_val) {}
void extend_left() {
if (left_child == nullptr) left_child = new node();
}
void extend_right() {
if (right_child == nullptr) right_child = new node();
}
};
node* root[maxn];
node* er;
node* build(int lo = 1, int hi = n) {
if (lo == hi) return new node();
node *cur = new node();
int mid = (lo + hi) >> 1;
cur->left_child = build(lo, mid);
cur->right_child = build(mid+1, hi);
return cur;
}
node* upd(int u, node *oldver, int lo = 1, int hi = n) {
if (lo == hi)
return new node(oldver->val + 1);
node *cur = new node();
int mid = (lo + hi) >> 1;
if (u <= mid) {
cur->left_child = upd(u, oldver->left_child, lo, mid);
cur->right_child = oldver->right_child;
} else {
cur->left_child = oldver->left_child;
cur->right_child = upd(u, oldver->right_child, mid+1, hi);
}
cur->val = cur->left_child->val + cur->right_child->val;
return cur;
}
//int get(int u, int v, node *cur, int lo = 1, int hi = n) {
// if (u <= lo && hi <= v) return cur->val;
// int mid = (lo + hi) >> 1;
// return (u <= mid ? get(u, v, cur->left_child, lo, mid) : 0) +
// (v > mid ? get(u, v, cur->right_child, mid+1, hi) : 0);
//}
void preprocess() {
vector<vector<int> > nho(n+1);
for (int i = 0; i < n; i++)
nho[a[i]].emplace_back(b[i]);
root[0] = build();
for (int i = 1; i <= n; i++) {
root[i] = root[i-1];
for (int j : nho[i]) root[i] = upd(j, root[i]);
}
}
void init(int N, int A[], int B[]) {
n = N;
for (int i = 0; i < N; i++) a[i] = A[i];
for (int i = 0; i < N; i++) b[i] = B[i];
preprocess();
}
void builderman(int k, node *cur, node *er, int lo = 1, int hi = n) {
if (lo == hi) {
er = cur;
return;
}
int mid = (lo + hi) >> 1, trai = cur->left_child->val;
if (k <= trai) {
er->extend_left(); er->extend_right();
builderman(k, cur->left_child, er->left_child, lo, mid);
}
else {
er->left_child = cur->left_child; er->extend_right();
builderman(k-trai, cur->right_child, er->right_child, mid+1, hi);
}
er->val = er->left_child->val + er->right_child->val;
}
int prefix_sum = 0;
int solve(int u) {
if (root[u]->val - er->val < u) return 0;
builderman(prefix_sum+u, root[u], er);
return 1;
}
int can(int M, int K[]) {
sort(K, K + M);
er = new node();
for (int i = 0; i < M; i++) {
if (K[i] > n) return 0;
if (!solve(K[i])) return 0;
prefix_sum += K[i];
}
return 1;
}
/*
4
1 2
2 3
2 3
2 4
2
2 1 3
2 1 1
*/
