#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];
class SegmentTree{
private:
int n;
std::vector<std::vector<int>> aint;
public:
SegmentTree(int n = 0){
this->n = n;
aint.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);
}
for(int i = from; i <= to; i++)
aint[node].push_back(v[i].y);
sort(aint[node].begin(), aint[node].end());
}
///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;
if(target < aint[node][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 + 1;
}
int query(int node, int from, int to, int x, int y, int target){
if(y < x)
return 0;
if(from == x && to == y)
return lowerthan(node, target);
else {
int mid = (from + to) / 2;
if(x <= mid && y <= mid)
return query(node * 2, from, mid, x, y, target);
else if(x <= mid && mid + 1 <= y)
return query(node * 2, from, mid, x, mid, target) + query(node * 2 + 1, mid + 1, to, mid + 1, y, target);
else if(mid + 1 <= x && mid + 1 <= y)
return query(node * 2 + 1, mid + 1, to, x, y, target);
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_;
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);
}
int cost[1 + nmax];
int pocket[1 + nmax];
void clean(int M, int K[]){
for(int i = 0; i < M; i++) {
cost[K[i]] = 0;
pocket[K[i]] = 0;
}
}
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, candidates[1] - 1);
for(int j = 1;j < candidates.size() - 1; j++){
int sum = aint.query(1, 1, N, last + 1, curr, candidates[j + 1] - 1);
pocket[candidates[j]] += aint.query(1, 1, N, last + 1, curr, candidates[j + 1] - 1) -
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]]){
clean(M, K);
return 0;
}
}
clean(M, K);
return 1;
}
