#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long int;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define F first
#define S second
ll min (ll x, ll y){
return ((x < y) ? x : y);
}
ll max (ll x, ll y){
return ((x > y) ? x : y);
}
struct PNode {
vi v,t;
ll qry (ll curt){
/*
cout << "queried: " << curt << "\n";
for (auto i: v) cout << i << " ";
cout << endl;
for (auto i: t) cout << i << " ";
cout << endl;
*/
auto itr = upper_bound(t.begin(),t.end(),curt);
ll idx = distance(t.begin(),itr)-1;
//cout << v[idx] << endl;
return v[idx];
}
ll lst_qry(){
return v.back();
}
void inc_update (ll vn, ll tn){
if (t.back() != tn){
v.push_back(lst_qry()+vn);
t.push_back(tn);
}else{
v[v.size()-1] += vn;
}
}
void change_update (ll vn, ll tn){
if (t.back() != tn){
v.push_back(vn);
t.push_back(tn);
}else{
v[v.size()-1] = vn;
}
}
PNode (){ v = vi{0}; t = vi{0}; }
};
class SegTree {
private:
vector<PNode> st;
ll n;
ll left (ll x){ return (x << 1) ; }
ll right (ll x){ return (x << 1) + 1; }
void update (ll i, ll l, ll r, ll idx, ll inc, ll t){
// assumed that t is updated increasingly
if (r >= idx && idx >= l){
if (l == r){
st[i].inc_update(inc,t);
}else{
//cout << i << " " << l << " -> " << r << " : " << st[i].lst_qry() << endl;
ll m = (l+r)/2;
update(left(i),l,m,idx,inc,t);
update(right(i),m+1,r,idx,inc,t);
st[i].change_update(st[left(i)].lst_qry()+st[right(i)].lst_qry(),t);
}
//cout << i << " " << t << " , " << l << " -> " << r << " : " << st[i].lst_qry() << endl;
}
}
ll query (ll i, ll l, ll r, ll ql, ll qr, ll t){
//cout << i << " " << l << " " << r << " " << ql << " " << qr << endl;
if (qr >= r && l >= ql){
/*
cout << "queried: \n";
cout << "params: " << i << " " << l << " " << r << endl;
cout << "result: " << st[i].qry(t) << endl;
*/
return st[i].qry(t);
}else if (l > qr || ql > r){
return 0;
}else{
ll m = (l+r)/2;
ll lres = 0, rres = 0;
if (!(l > qr || ql > m)) lres = query(left(i),l,m,ql,qr,t);
if (!(m+1 > qr || ql > r)) rres = query(right(i),m+1,r,ql,qr,t);
return lres+rres;
}
}
public:
SegTree (){}
SegTree(ll _n): n(_n){
st.resize(4*n);
}
void update (ll idx, ll inc, ll t){
update(1,0,n-1,idx,inc,t);
}
ll query (ll ql, ll qr, ll t){
return query(1,0,n-1,ql,qr,t);
}
};
SegTree st;
ll n;
void init(int _n, int a[], int b[]) {
n = _n;
st = SegTree(n+1);
vii itvls;
for (ll i = 0; n > i; i++) itvls.emplace_back(a[i],b[i]);
sort(itvls.begin(),itvls.end());
for (auto i: itvls){
//cout << i.F << " " << i.S << endl;
st.update(i.S,1,i.F);
}
}
vi ctr,vals,byBucket;
int can(int m, int k[]) {
sort(k,k+m);
vi().swap(ctr);
ctr.push_back(k[0]);
for (ll i = 1; m > i; i++){
if (k[i] != k[i-1]) ctr.push_back(0);
ctr[ctr.size()-1] += k[i];
}
vi().swap(vals);
vals.push_back(k[0]);
for (ll i = 1; m > i; i++){
if (k[i] != k[i-1]) vals.push_back(k[i]);
}
vals.push_back(n+1);
vi byBucket;
byBucket.assign(vals.size(),0);
/*
cout << itr->F << " " << itr->S << endl;
cout << "vals:\n";
for (auto i: vals) cout << i << " ";
cout << endl;
*/
for (ll i = 0; vals.size() > i+1; i++){
for (ll j = i; vals.size() > j+1; j++){
//cout << "i: " << i << " j: " << j << endl;
ll rmv = st.query(vals[j],vals[j+1]-1,vals[i])-byBucket[j];
//cout << vals[j] << " " << vals[j+1] << " " << vals[i] << ": " << rmv << endl;
//cout << "itr: " << itr->F << " " << itr->S << endl;
rmv = min(rmv,ctr[i]);
ctr[i] -= rmv;
byBucket[j] += rmv;
}
/*
cout << itr->F << " " << itr->S << endl;
for (auto i: byBucket) cout << i << " ";
cout << endl;
*/
}
for (auto i: ctr){
//cout << i.F << " " << i.S << endl;
if (i > 0){ return 0; }
}
//cout << "1\n";
return 1;
}
