#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
typedef pair<int,int> ii;
typedef pair<ii,int> iiI;
#define fi first
#define se second
struct persistentSeg{
struct node{
int val, Lnode, Rnode;
};
node seg[N * 25];
int root[N];
int totalNode;
persistentSeg(){
for(int i=1;i<=2000000;i++){
seg[i].Lnode = 2*i;
seg[i].Rnode = 2*i+1;
}
root[0] = 1;
totalNode = 2000000;
}
int upd(int id,int l,int r,int pos,int value){
int newNode = ++totalNode;
seg[newNode] = seg[id];
if (l == r){
seg[newNode].val += value;
return newNode;
}
int mid = (l+r)/2;
if (pos <= mid){
seg[newNode].Lnode = upd(seg[newNode].Lnode, l, (l+r)/2, pos, value);
}
else{
seg[newNode].Rnode = upd(seg[newNode].Rnode, (l+r)/2+1, r, pos, value);
}
seg[newNode].val = seg[seg[newNode].Lnode].val + seg[seg[newNode].Rnode].val;
return newNode;
}
int get(int id,int l,int r,int u,int v){
if (v < l || r < u)
return 0;
if (u <= l && r <= v)
return seg[id].val;
return get(seg[id].Lnode, l, (l+r)/2, u, v) + get(seg[id].Rnode, (l+r)/2+1, r, u, v);
}
};
int n;
ii range[N];
persistentSeg seg;
vector <int> lis[N];
void init(int nn, int A[], int B[]) {
n = nn;
for(int i=0;i<n;i++){
lis[A[i]].push_back(B[i]);
}
for(int i=1;i<=n;i++){
seg.root[i] = seg.root[i-1];
for(auto v: lis[i])
seg.root[i] = seg.upd(seg.root[i], 1, n, v, 1);
}
}
iiI del[500]; int delSz;
int currentInRange(int curRootId,int L,int R){
int res = 0, cur = L;
for(int i=delSz-1;;i--){
res += seg.get(seg.root[curRootId], 1, n, cur, min(del[i].fi.fi, R))
- seg.get(seg.root[del[i].fi.se], 1, n, cur, min(del[i].fi.fi, R));
res += (min(del[i].fi.fi, R) == del[i].fi.fi) * del[i].se;
cur = del[i].fi.fi+1;
if (cur > R) break;
}
return res;
}
int can(int m, int lst[]) {
//~~~~~~~~~~~~~~~~prep~~~~~~~~~~~~~~~~~~~~~~
set <int> s;
int tmp = 0;
for(int i=0;i<m;i++){
tmp = min(n+1, tmp + lst[i]);
s.insert(lst[i]);
}
if (tmp > n)
return 0;
int newM = 0;
int ask[s.size()+5] = {}, askTimes[s.size()+5] = {};
for(set<int>::iterator it = s.begin(); it != s.end(); it++){
ask[++newM] = *it;
}
for(int i=0;i<m;i++){
askTimes[lower_bound(ask+1,ask+newM+1,lst[i]) - ask] ++;
}
//~~~~~~~~~~~~~~~solve~~~~~~~~~~~~~~~~~~~~~
delSz = 0;
del[delSz++] = iiI({{n, 0}, 0});
for(int i=1;i<=newM;i++){
while(delSz && del[delSz-1].fi.fi < ask[i]) delSz--;
int L = ask[i]-1, R = n;
while(L+1<R){
int mid = (L+R)/2;
if (currentInRange(ask[i], ask[i], mid) < ask[i] * askTimes[i])
L = mid;
else
R = mid;
}
int curRes = currentInRange(ask[i], ask[i], R);
if (curRes < ask[i] * askTimes[i]) return 0;
while(delSz && del[delSz-1].fi.fi <= R) delSz--;
del[delSz++] = iiI({ii(R, ask[i]), curRes - ask[i] * askTimes[i]});
}
return 1;
}
