#include "teams.h"
#include <algorithm>
#include <vector>
#include <iostream>
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;
int left = -1, right = -1;
};
struct Interval
{
int left, right;
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);
}
};
struct Stop
{
Stop(int p, int u, int k) : pos(p), used(u), keep(k) {}
int pos, used, keep;
};
const int MAXN = 5e5 + 1;
int students;
const int LEAVES = 1 << 19;
const Interval ROOTCOVER = { 0, LEAVES };
std::vector<int> interEnds[MAXN];
int root[MAXN];
std::vector<Node> tree;
int makeleft(int node)
{
if (tree[node].left == -1)
{
tree.emplace_back(tree[node].date);
tree[node].left = (int)tree.size() - 1;
}
else if (tree[node].date != tree[tree[node].left].date)
{
tree.emplace_back(tree[tree[node].left], tree[node].date);
tree[node].left = (int)tree.size() - 1;
}
return tree[node].left;
}
int getleft(int node)
{
if (node == -1)
return -1;
return tree[node].left;
}
int makeright(int node)
{
if (tree[node].right == -1)
{
tree.emplace_back(tree[node].date);
tree[node].right = (int)tree.size() - 1;
}
else if (tree[node].date != tree[tree[node].right].date)
{
tree.emplace_back(tree[tree[node].right], tree[node].date);
tree[node].right = (int)tree.size() - 1;
}
return tree[node].right;
}
int getright(int node)
{
if (node == -1)
return -1;
return tree[node].right;
}
int read(int front, int back)
{
if (front == -1)
return 0;
if (back == -1)
return tree[front].value;
return (tree[front].value - tree[back].value);
}
void add(int node, Interval covered, Interval requested)
{
tree[node].value++;
if (!covered.IsIncludedIn(requested))
{
if (!covered.Left().IsDisjointFrom(requested))
add(makeleft(node), covered.Left(), requested);
if (!covered.Right().IsDisjointFrom(requested))
add(makeright(node), covered.Right(), requested);
}
}
Stop search(int front, int back, Interval covered, Interval requested, int needed)
{
if (covered.IsIncludedIn(requested))
{
int sum = read(front, back);
if (sum < needed)
return Stop(covered.right, sum, 0);
if (covered.right - covered.left == 1)
return Stop(covered.left, needed, needed);
}
else if (covered.IsDisjointFrom(requested))
{
return Stop(covered.left, 0, 0);
}
Stop lft = search(getleft(front), getleft(back), covered.Left(), requested, needed);
if (lft.used == needed)
return lft;
Stop rgt = search(getright(front), getright(back), covered.Right(), requested, needed - lft.used);
return Stop(rgt.pos, lft.used + rgt.used, rgt.keep);
}
void init(int N, int A[], int B[])
{
students = N;
for (int iStud = 0; iStud < students; iStud++)
interEnds[A[iStud]].emplace_back(B[iStud]);
tree.emplace_back(0);
for (int iStart = 1; iStart <= students; iStart++)
{
tree.emplace_back(tree[root[iStart - 1]], iStart);
root[iStart] = (int)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);
std::vector<Stop> stops;
stops.emplace_back(MAXN, 0, 0);
for (int iGroup = 0; iGroup < M; iGroup++)
{
int needed = K[iGroup], start = K[iGroup];
while (needed > 0)
{
if (stops.empty())
return 0;
Stop last = stops.back();
if (last.pos < start)
{
stops.pop_back();
continue;
}
Stop result = search(root[K[iGroup]], root[last.used], ROOTCOVER, Interval(start, last.pos), needed);
needed -= result.used;
if (needed == 0)
stops.emplace_back(result.pos, K[iGroup], result.keep);
else
{
start = last.pos;
needed += last.keep;
stops.pop_back();
}
}
}
return 1;
}
