#include "teams.h"
#include <vector>
#include <algorithm>
#include <cassert>
#include <iostream>
using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
int const nmax = 500000;
struct Child{
int x;
int y;
bool operator < (Child const &a) const{
return x < a.x;
}
} v[1 + nmax];
int jumpsize[1 + nmax];
class SegmentTree{
private:
int n;
std::vector<std::vector<int>> aint;
std::vector<std::vector<int>> leftedge, rightedge;
public:
SegmentTree(int n = 0){
this->n = n;
aint.resize(4 * n);
leftedge.resize(4 * n);
rightedge.resize(4 * n);
}
void build(int node, int from, int to){
if(from < to){
int mid = (from + to) / 2;
build(node * 2, from, mid);
build(node * 2 + 1, mid + 1, to);
aint[node].push_back(0);
aint[node].resize(to - from + 2);
merge(aint[node * 2].begin() + 1, aint[node * 2].end(), aint[node * 2 + 1].begin() + 1, aint[node * 2 + 1].end(), aint[node].begin() + 1);
leftedge[node].resize(to - from + 2);
rightedge[node].resize(to - from + 2);
//std::cout << ":";
int ptr = 0;
//std::cout << leftedge[node].size() << " " << aint[node].size() << '\n';
for(int i = 0; i < leftedge[node].size(); i++){
while(ptr + 1 < aint[node * 2].size() && aint[node * 2][ptr + 1] <= aint[node][i])
ptr++;
leftedge[node][i] = ptr;
}
//std::cout << "*";
ptr = 0;
for(int i = 0; i < rightedge[node].size(); i++){
while(ptr + 1 < aint[node * 2 + 1].size() && aint[node * 2 + 1][ptr + 1] <= aint[node][i])
ptr++;
rightedge[node][i] = ptr;
}
//std::cout << "|";
} else {
aint[node].push_back(0);
aint[node].push_back(v[from].y);
}
/*
std::cout << node << " " << from << " " << to << '\n';
for(int i = 0; i < aint[node].size(); i++)
std::cout << aint[node][i] << " ";
std::cout << '\n';
for(int i = 0; i < leftedge[node].size(); i++)
std::cout << leftedge[node][i] << " ";
std::cout << '\n';
for(int i = 0; i < rightedge[node].size(); i++)
std::cout << rightedge[node][i] << " ";
std::cout << '\n' << '\n';
//*/
}
///counts how many values are lower(or equal) than target in node
int lowerthan(int node, int target){
if(aint[node].size() == 0)
return 0;
int x = 0;
for(int jump = (1 << 20); 0 < jump; jump /= 2)
if(x + jump < aint[node].size() && aint[node][x + jump] <= target)
x += jump;
return x;
}
int query(int node, int from, int to, int x, int y, int pos){
if(y < x)
return 0;
if(from == x && to == y)
return pos;
else {
int mid = (from + to) / 2;
if(x <= mid && y <= mid)
return query(node * 2, from, mid, x, y, leftedge[node][pos]);
else if(x <= mid && mid + 1 <= y)
return query(node * 2, from, mid, x, mid, leftedge[node][pos]) + query(node * 2 + 1, mid + 1, to, mid + 1, y, rightedge[node][pos]);
else if(mid + 1 <= x && mid + 1 <= y)
return query(node * 2 + 1, mid + 1, to, x, y, rightedge[node][pos]);
else{
///Something is definitely wrong
assert(1 < 0);
return 0;
}
}
}
};
int N;
SegmentTree aint;
int pos[1 + nmax];
void init(int N_, int A[], int B[]) {
N = N_;
jumpsize[1] = 1;
for(int i = 2;i <= N; i++)
jumpsize[i] = jumpsize[i / 2] * 2;
for(int i = 1;i <= N; i++)
v[i] = {A[i - 1], B[i - 1]};
std::sort(v + 1, v + N + 1);
int ptr = 0;
for(int i = 1;i <= N; i++){
while(ptr < N && v[ptr + 1].x <= i)
ptr++;
pos[i] = ptr;
}
aint = SegmentTree(N);
aint.build(1, 1, N);
assert(N < 200000);
}
int cost[1 + nmax];
int pocket[1 + nmax];
int can(int M, int K[]) {
int sum = 0;
for(int i = 0; i < M; i++)
sum += K[i];
if(N < sum)
return 0;
std::vector<int> candidates;
candidates.push_back(0);
candidates.push_back(N + 1);
for(int i = 0; i < M; i++){
candidates.push_back(K[i]);
cost[K[i]] += K[i];
}
std::sort(candidates.begin(), candidates.end());
candidates.erase(unique(candidates.begin(), candidates.end()) , candidates.end());
for(int i = 1; i < candidates.size() - 1; i++){
int last = pos[candidates[i - 1]];
int curr = pos[candidates[i]];
int lastsum = aint.query(1, 1, N, last + 1, curr, aint.lowerthan(1, candidates[i] - 1));
for(int j = i;j < candidates.size() - 1; j++){
int sum = aint.query(1, 1, N, last + 1, curr, aint.lowerthan(1, candidates[j + 1] - 1));
pocket[candidates[j]] += sum - lastsum;
lastsum = sum;
}
for(int j = i; j < candidates.size(); j++){
if(0 < cost[candidates[i]] && 0 < pocket[candidates[j]]){
int val = MIN(cost[candidates[i]], pocket[candidates[j]]);
cost[candidates[i]] -= val;
pocket[candidates[j]] -= val;
}
}
if(0 < cost[candidates[i]]){
for(int i = 0; i < M; i++) {
cost[K[i]] = 0;
pocket[K[i]] = 0;
}
return 0;
}
}
for(int i = 0; i < M; i++) {
cost[K[i]] = 0;
pocket[K[i]] = 0;
}
return 1;
}
