#include <bits/stdc++.h>
using namespace std;
#include "teams.h"
struct FenwickTree2dOff
{
vector<vector<int>> t, c;
bool initialized = 0;
FenwickTree2dOff() {}
FenwickTree2dOff(int64_t n)
{
t = vector<vector<int>>(n);
c = vector<vector<int>>(n);
}
void initialize()
{
for (int64_t i = 0; i < t.size(); i++)
{
sort(c[i].begin(), c[i].end());
c[i].resize(unique(c[i].begin(), c[i].end()) - c[i].begin());
t[i] = vector<int>(c[i].size(), 0);
}
initialized = 1;
}
void increment(int64_t i, int64_t j, int x)
{
i++, j++;
while (i <= t.size())
{
if (!initialized)
c[i - 1].push_back(j);
else
{
int64_t u = upper_bound(c[i - 1].begin(), c[i - 1].end(), j) - c[i - 1].begin();
while (u <= t[i - 1].size())
{
t[i - 1][u - 1] += x;
u += u & -u;
}
}
i += i & -i;
}
}
int prefix_sum(int64_t i, int64_t j)
{
i++, j++;
int x = 0;
while (i)
{
int64_t u = upper_bound(c[i - 1].begin(), c[i - 1].end(), j) - c[i - 1].begin();
while (u)
{
x += t[i - 1][u - 1];
u -= u & -u;
}
i -= i & -i;
}
return x;
}
int sum(int64_t i1, int64_t j1, int64_t i2, int64_t j2)
{
return prefix_sum(i2, j2) - prefix_sum(i1 - 1, j2) -
prefix_sum(i2, j1 - 1) + prefix_sum(i1 - 1, j1 - 1);
}
};
FenwickTree2dOff tree;
int n;
void init(int N, int A[], int B[])
{
n = N;
tree = FenwickTree2dOff(N + 2);
for (int64_t i = 0; i < N; i++)
tree.increment(A[i], B[i], 1);
tree.initialize();
for (int64_t i = 0; i < N; i++)
tree.increment(A[i], B[i], 1);
}
int can(int M, int K[])
{
sort(K, K + M);
int y_lim = 1, residual = 0;
for (int64_t i = 0; i < M; i++)
{
if (K[i] <= residual)
{
residual -= K[i];
continue;
}
int a = max(y_lim, K[i]), b = n + 1, last_num = 0;
while (a < b) // Binary search for the highest end index needed.
{
int const y = (a + b) / 2;
int const x = tree.sum(1, y_lim, K[i], y);
if (x >= K[i] - residual)
b = y, last_num = x;
else
a = y + 1;
}
if (a == n + 1)
return 0;
residual = last_num - (K[i] - residual);
y_lim = a + 1;
}
return 1;
}
