#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
int n;
int cntRig[N];
vector <int> lef[N];
int ver[N];
#define mid ((l + r) >> 1)
struct PersistentIT {
int T[N * 30], L[N * 30], R[N * 30], peak;
int build(int l, int r) {
if (l == r) {
++peak; L[peak] = R[peak] = peak; return peak;
}
int u = ++peak;
L[u] = build(l, mid);
R[u] = build(mid + 1, r);
return u;
}
int upd(int v, int l, int r, int x, int val) { // a[x] += val
if (r < x || l > x) return v;
if (l == r) {
++peak; T[peak] = T[v] + val; L[peak] = R[peak] = peak; return peak;
}
int u = ++peak;
L[u] = upd(L[v], l, mid, x, val);
R[u] = upd(R[v], mid + 1, r, x, val);
T[u] = T[L[u]] + T[R[u]];
//printf("u = %d l = %d r = %d -> leftchild = %d rightchild = %d => T = %d\n", u, l, r, L[u], R[u], T[u]);
return u;
}
} pit;
struct IT {
int T[N << 2];
vector < pair<int,int> > buf; // history
void upd(int v, int l, int r, int x, int val) {
if (r < x || l > x) return;
if (l == r) { if (val > 0) buf.push_back(make_pair(x, val)); T[v] += val; return; }
upd(v << 1, l, mid, x, val);
upd(v << 1 | 1, mid + 1, r, x, val);
T[v] = T[v << 1] + T[v << 1 | 1];
}
void reset() {
while(buf.size()) {
auto i = buf.back(); buf.pop_back();
upd(1, 1, n, i.first, -i.second);
}
}
} it;
// --------------------------------
void init(int _n, int A[], int B[]) {
n = _n;
for (int i = 0; i < n; ++i) {
cntRig[B[i]]++;
lef[A[i]].push_back(B[i]);
}
pit.build(1, n);
ver[0] = 1;
for (int i = 1; i <= n; ++i) {
ver[i] = ver[i - 1];
if (cntRig[i - 1]) {
ver[i] = pit.upd(ver[i], 1, n, i - 1, -cntRig[i - 1]); // delete
}
for (auto &j : lef[i]) {
ver[i] = pit.upd(ver[i], 1, n, j, +1); // add
}
}
}
int find(int pv, int v, int l, int r, int leftmost) {
// pv is the index in PIT, v is the index in IT
// find the smallest i >= leftmost such that pit[i] - it[i] > 0
if (r < leftmost) return 0;
if (l >= leftmost) {
if (l == r) {
if (pit.T[pv] > it.T[v]) return l;
else return 0;
}
if (pit.T[pv] <= it.T[v]) return 0;
}
int ret = find(pit.L[pv], v << 1, l, mid, leftmost);
if (!ret) return find(pit.R[pv], v << 1 | 1, mid + 1, r, leftmost);
else return ret;
}
int can(int m, int sz[]) {
sort(sz, sz + m);
for (int i = 0; i < m; ++i) {
int s = sz[i];
while(sz[i]--) {
int pos = find(ver[s], 1, 1, n, s);
if (pos == 0) {
it.reset();
return false;
}
it.upd(1, 1, n, pos, +1);
}
}
it.reset();
return true;
}
