#include "teams.h"
#include <algorithm>
#include <queue>
struct Node
{
Node(int d) : date(d) {}
Node(const Node &prev, int newDate)
{
value = prev.value;
date = newDate;
left = prev.left;
right = prev.right;
}
int value = 0, date = 0;
int left = -1, right = -1;
};
class Interval
{
int left, right;
public:
Interval(int l, int r) : left(l), right(r) {}
bool IsIncludedIn(const Interval &other) const
{
return (other.left <= left && right <= other.right);
}
bool IsDisjointFrom(const Interval &other) const
{
return (other.right <= left || right <= other.left);
}
Interval Left() const
{
return Interval(left, (left + right) / 2);
}
Interval Right() const
{
return Interval((left + right) / 2, right);
}
};
const int MAXN = 5e5;
int students;
const int LEAVES = 1 << 19;
const Interval ROOTCOVER = { 0, LEAVES };
std::vector<int> interEnds[MAXN];
int root[MAXN];
std::vector<Node> tree;
void add(int node, Interval covered, Interval requested)
{
if (covered.IsDisjointFrom(requested))
return;
tree[node].value++;
if (!covered.IsIncludedIn(requested))
{
if (tree[node].left == -1)
{
tree.emplace_back(tree[node].date);
tree[node].left = tree.size() - 1;
}
else if (tree[tree[node].left].date != tree[node].date)
{
tree.emplace_back(tree[tree[node].left], tree[node].date);
tree[node].left = tree.size() - 1;
}
if (tree[node].right == -1)
{
tree.emplace_back(tree[node].date);
tree[node].right = tree.size() - 1;
}
else if (tree[tree[node].right].date != tree[node].date)
{
tree.emplace_back(tree[tree[node].right], tree[node].date);
tree[node].right = tree.size() - 1;
}
add(tree[node].left, covered.Left(), requested);
add(tree[node].right, covered.Right(), requested);
}
}
int count(int node, Interval covered, Interval requested)
{
if (node == -1 || covered.IsDisjointFrom(requested))
return 0;
if (covered.IsIncludedIn(requested))
return tree[node].value;
return (count(tree[node].left, covered.Left(), requested) + count(tree[node].right, covered.Right(), requested));
}
void init(int N, int A[], int B[])
{
students = N;
for (int iStud = 0; iStud < students; iStud++)
interEnds[A[iStud] - 1].emplace_back(B[iStud] - 1);
for (int iStart = 0; iStart < students; iStart++)
{
if (iStart == 0)
{
tree.emplace_back(0);
root[iStart] = 0;
}
else
{
tree.emplace_back(tree[root[iStart - 1]], iStart);
root[iStart] = tree.size() - 1;
}
for (int end : interEnds[iStart])
add(root[iStart], ROOTCOVER, Interval(end, end + 1));
}
}
int can(int M, int K[])
{
std::sort(K, K + M);
int used = 0, lastSeen = -1;
for (int iGroup = M - 1; iGroup > -1; iGroup--)
{
K[iGroup]--;
if (iGroup < M - 1)
used = std::max(0, used - lastSeen + count(root[K[iGroup]], ROOTCOVER, Interval(K[iGroup + 1], students)));
lastSeen = count(root[K[iGroup]], ROOTCOVER, Interval(K[iGroup], students));
if (lastSeen - used <= K[iGroup])
return 0;
used += K[iGroup] + 1;
}
return 1;
}
