#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn = 5e5 + 100;
int N;
vector<pair<int, int>> A;
struct Node {
int sz, mnA, mxB, lz;
vector<pair<int, int>> A;
};
struct SGT {
vector<Node> sgt;
SGT(int sz) {
sgt.resize(4 * sz);
}
Node merge(Node a, Node b) {
Node ans;
ans.sz = {a.sz + b.sz};
vector<pair<int, int>> v;
for (auto x : a.A) v.push_back(x);
for (auto x : b.A) v.push_back(x);
sort(v.begin(), v.end());
ans.A = v;
ans.mnA = min(a.mnA, b.mnA);
ans.mxB = max(a.mxB, b.mxB);
return ans;
}
void build(int k, int l, int r) {
if (l == r) {
sgt[k].sz = 1;
sgt[k].A.push_back({A[l].first, 1});
sgt[k].mnA = A[l].first;
sgt[k].mxB = A[l].second;
return;
}
int mid = (l + r) / 2;
build(k * 2, l, mid);
build(k * 2 + 1, mid + 1, r);
sgt[k] = merge(sgt[k * 2], sgt[k * 2 + 1]);
}
void push(int k, int l, int r) {
if (sgt[k].lz == 1) {
sgt[k * 2].lz = sgt[k * 2 + 1].lz = 1;
for (auto x : sgt[k].A) x.second = 1;
sgt[k].sz = r - l + 1;
}
if (sgt[k].lz == -1) {
sgt[k * 2].lz = sgt[k * 2 + 1].lz = -1;
for (auto x : sgt[k].A) x.second = 0;
sgt[k].sz = 0;
}
sgt[k].lz = 0;
}
int get(int k, int l, int r, int i, int sz) {
push(k, l, r);
if (sgt[k].mnA > i || sgt[k].mxB < i || !sgt[k].sz) return 0;
int mid = (l + r) / 2;
if (sgt[k].mnA <= i && sgt[k].mxB >= i) {
if (sgt[k].sz <= sz && sgt[k].sz == r - l + 1) {
int SZ = sgt[k].sz;
sgt[k].lz = -1;
push(k, l, r);
return SZ;
}
int ans = get(k * 2 + 1, mid + 1, r, i, sz);
sgt[k] = merge(sgt[k * 2], sgt[k * 2 + 1]);
if (ans == sz) return ans;
ans += get(k * 2, l, mid, i, sz - ans);
sgt[k] = merge(sgt[k * 2], sgt[k * 2 + 1]);
return ans;
}
int ans = get(k * 2, l, mid, i, sz);
if (ans != sz) ans += get(k * 2 + 1, mid + 1, r, i, sz - ans);
sgt[k] = merge(sgt[k * 2], sgt[k * 2 + 1]);
return ans;
}
} sgt(mxn);
void init(int _N, int _A[], int _B[]) {
N = _N;
for (int i = 0; i < N; i++) A.push_back({_A[i], _B[i]});
sort(A.begin(), A.end(), [&] (pair<int, int> a, pair<int, int> b) {
return a.second < b.second;
});
sgt.build(1, 0, N - 1);
}
int can(int M, int K[]) {
vector<int> v;
for (int i = 0; i < M; i++) v.push_back(K[i]);
sort(v.begin(), v.end());
sgt.sgt[1].lz = 1;
for (int i = 0; i < M; i++) {
int people = sgt.get(1, 0, N - 1, v[i], v[i]);
if (people != v[i]) return 0;
}
return 1;
}
