// moreflags=grader.cpp
//
// 10
// that bug would be terrible to debug without a generator...?
#include "teams.h"
#include<vector>
#include<queue>
#include<functional>
#include<algorithm>
#include<numeric>
#if LOCAL
#include<iostream>
#else
#define NDEBUG
#endif
#include<cassert>
struct Persistent{
struct Node{int value; std::array<int, 2> children;};
// value is sum of current subtree
std::vector<Node> data;
int number;
Persistent(int number=0): number(number){
data.resize(number*4);
for(int node=0; node<(int)data.size()/2; ++node)
data[node].children={node*2+1, node*2+2};
// initially root is 0 and all values are 0
}
int makeNode(Node node){
int const result=(int)data.size();
data.push_back(node);
return result;
}
int set(int node, int left, int right, int index, auto getter /* old -> new */){
if(left+1==right){
//if(data[node].value==value) return node;
return makeNode(Node{getter(data[node].value), {}});
}
int const middle=(left+right)>>1;
auto copy=data[node];
if(index>=middle){
copy.value-=data[copy.children[1]].value;
copy.children[1]=set(copy.children[1], middle, right, index, getter);
copy.value+=data[copy.children[1]].value;
}else{
copy.value-=data[copy.children[0]].value;
copy.children[0]=set(copy.children[0], left, middle, index, getter);
copy.value+=data[copy.children[0]].value;
}
return makeNode(copy);
}
int set(int node, int index, auto getter /* old -> new */){
return set(node, 0, number, index, getter);
}
int getInternal(int node, int left, int right, int queryLeft, int queryRight)const{
if(queryLeft>=right or queryRight<=left) return 0;
if(queryLeft<=left and right<=queryRight) return data[node].value;
int const middle=(left+right)>>1;
return getInternal(data[node].children[0], left, middle, queryLeft, queryRight)+
getInternal(data[node].children[1], middle, right, queryLeft, queryRight);
}
int get(int node, int queryLeft, int queryRight)const{
return getInternal(node, 0, number, queryLeft, queryRight);
}
int getInternal(int node, int left, int right, int queryLeft)const{
if(queryLeft>=right) return 0;
if(queryLeft<=left) return data[node].value;
int const middle=(left+right)>>1;
return getInternal(data[node].children[0], left, middle, queryLeft)+
getInternal(data[node].children[1], middle, right, queryLeft);
}
int get(int node, int queryLeft)const{ // equal to queryRight==number
return getInternal(node, 0, number, queryLeft);
}
};
std::vector<std::pair<int, int>> students;
Persistent tree;
std::vector<int> roots;
std::vector<int> bounds;
// students[bounds[i-1]..bounds[i]].left = i
std::vector<char> possible;
int can(int M, int K[]) {
if(std::accumulate(K, K+M, (int64_t)0)>(int)students.size()) return 0;
for(int index=0; index<M; ++index) if(not possible[K[index]]) return 0;
std::sort(K, K+M);
struct Item{
int value;
mutable int count;
bool operator<(Item other) const{return value>other.value;}
};
std::priority_queue<Item> rights;
//std::map<int, int> rights;
std::vector<int> splits(K, K+M);
splits.erase(std::unique(begin(splits), end(splits)), end(splits));
int last=0;
for(int index=0; index<M; ++index){
auto const k=K[index];
if(k>(int)students.size()) return 0;
while(not rights.empty() and rights.top().value<k)
rights.pop();
auto j=int(std::lower_bound(begin(splits), end(splits), k)-begin(splits));
assert(splits[j]==k);
/*
if((bounds[k]-last)<=((int)splits.size()-j))
{
for(int index=last; index<bounds[k]; ++index)
if(students[index].second>=k)
rights.push({students[index].second, 1});
}else{
*/
auto const get=[&](int index){
return tree.get(roots[bounds[k]], splits[index])-tree.get(roots[last], splits[index]);
};
auto const extract=[&](auto extract, int updateLeft, int updateRight, int valueLeft, int valueRight){
assert(updateLeft<updateRight);
assert(valueLeft>=valueRight);
if(valueLeft==valueRight)
return;
if(updateLeft+1==updateRight){
rights.push({splits[updateLeft], valueLeft-valueRight});
return;
}
auto const updateMiddle=(updateLeft+updateRight)>>1;
int const valueMiddle=get(updateMiddle);
extract(extract, updateLeft, updateMiddle, valueLeft, valueMiddle);
extract(extract, updateMiddle, updateRight, valueMiddle, valueRight);
};
extract(extract, j, (int)splits.size(), get(j), 0);
//}
assert(last<=bounds[k]);
last=bounds[k];
int remain=k;
while(remain){
if(rights.empty()) return 0;
if(remain>=rights.top().count){
remain-=rights.top().count;
rights.pop();
}else{
rights.top().count-=remain;
break;
}
}
}
return 1;
}
void init(int N, int A[], int B[]) {
students.clear(); students.reserve(N);
for(int i=0; i<N; ++i)
students.push_back({A[i], B[i]});
std::sort(begin(students), end(students));
roots.reserve((int)students.size());
roots.clear();
roots.push_back(0);
tree=Persistent(N+1);
for(auto [left, right]: students){
assert(right<=N); assert(0<left);
roots.push_back(
tree.set(roots.back(), right, [&](int value){return value+1;})
);
}
if(0)
assert(([&]{
for(auto root: roots){
for(int index=0; index<tree.number; ++index)
std::cerr<<tree.get(root, index, index+1)<<' ';
std::cerr<<" -- ";
for(int index=0; index<tree.number; ++index)
std::cerr<<tree.get(root, index, tree.number)<<' ';
std::cerr<<'\n';
}
return true;
}()));
bounds.clear();
bounds.reserve(N+1);
for(int index=0; index<(int)students.size(); ++index)
while((int)bounds.size()<students[index].first)
bounds.push_back(index);
while((int)bounds.size()<N+1) bounds.push_back((int)students.size());
possible.assign(students.size()+1, true);
for(int index=1; index<=(int)students.size(); ++index)
if(not can(1, &index)) possible[index]=false;
}
