#pragma GCC optimize("unroll-loops,Ofast,O3")
#include <bits/stdc++.h>
#include "happiness.h"
#define pb push_back
#define mp make_pair
#define ll long long
using namespace std;
struct Node{
ll sum=0, l, r;
Node *lc = nullptr, *rc = nullptr;
Node(ll l, ll r) : l(l), r(r) {}
void extend(){
if(!lc && l<r){
ll m = (l+r)>>1;
lc = new Node(l, m);
rc = new Node(m+1, r);
}
}
void add(ll tar, ll val){
extend();
sum += val;
if(lc){
if(tar <= lc->r) lc->add(tar, val);
else rc->add(tar,val);
}
}
ll query(ll ql, ll qr){
if(ql<=l && r<=qr) return sum;
if(l>qr || r<ql) return 0;
extend();
return lc->query(ql, qr) + rc->query(ql, qr);
}
};
Node *root;
bool is_happy(int event, int coinsCount, long long coins[]){
for(int i=0; i<coinsCount; i++) root->add(coins[i], coins[i] * event);
ll x = 1;
while(x <= root->sum){
ll res = root->query(1, x);
if(res < x) return false;
x = res + 1;
}
return true;
}
bool init(int coinsCount, long long maxCoinSize, long long coins[]){
root = new Node(1, maxCoinSize);
return is_happy(1, coinsCount, coins);
}
