#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 5e5, MAX_SEG = 1e7, B_SIZE = 800;
int cnt = 1, seg_val[MAX_SEG], left_c[MAX_SEG], right_c[MAX_SEG];
struct Segtree {
map<int, int> points[MAX_N + 1];
int roots[MAX_N + 2];
void build() {
for (int i = 1; i <= MAX_N; i++) {
roots[i + 1] = roots[i];
for (pair<int, int> j : points[i]) update(j.first, j.second, roots[i + 1]);
}
}
void update(int pos, int val, int &node, int l = 1, int r = MAX_N) {
seg_val[cnt] = seg_val[node] + val;
left_c[cnt] = left_c[node];
right_c[cnt] = right_c[node];
node = cnt++;
if (l == r) return;
int mid = (l + r) / 2;
if (pos > mid) update(pos, val, right_c[node], mid + 1, r);
else update(pos, val, left_c[node], l, mid);
}
int query(int a, int b, int node, int l, int r) {
if (a > r || b < l) return 0;
if (a <= l && b >= r) return seg_val[node];
int mid = (l + r) / 2;
return query(a, b, left_c[node], l, mid) + query(a, b, right_c[node], mid + 1, r);
}
int query(int a1, int a2, int b1, int b2) {
return query(a1, a2, roots[b2 + 1], 1, MAX_N) - query(a1, a2, roots[b1], 1, MAX_N);
}
} segtree;
int N, dp[MAX_N];
multiset<pair<int, int>> students;
bool visited[MAX_N];
void init(int N, int A[], int B[]) {
::N = N;
for (int i = 0; i < N; i++) {
students.insert({B[i], A[i]});
segtree.points[B[i]][A[i]]++;
}
segtree.build();
}
int can(int M, int K[]) {
sort(K, K + M);
if (M > B_SIZE) {
multiset<pair<int, int>> cp = students;
for (int i = 0; i < M; i++) {
vector<pair<int, int>> to_remove;
for (pair<int, int> j : cp) {
if (K[i] <= j.first && K[i] >= j.second) to_remove.push_back(j);
if (to_remove.size() == K[i]) break;
}
if (to_remove.size() != K[i]) return 0;
for (pair<int, int> j : to_remove) cp.erase(cp.find(j));
}
return 1;
} else {
for (int i = 0; i < M; i++) {
dp[i] = segtree.query(1, K[i], K[i], N) - K[i];
for (int j = 0; j < i; j++) {
dp[i] = min(dp[i], dp[j] + segtree.query(K[j] + 1, K[i], K[i], N) - K[i]);
}
if (dp[i] < 0) return 0;
}
return 1;
}
}
