#include "happiness.h"
using ll = long long;
struct Node {
ll sum, l, r;
Node *lc, *rc;
Node(ll tl, ll tr) : sum(0), l(tl), r(tr), lc(nullptr), rc(nullptr) {}
void update(ll pos, ll val) {
if(r < pos && l > pos) return;
this->sum += val;
if(l == r) return ;
int tm = (l + r) / 2;
if(pos <= tm) {
if(!lc) this->lc = new Node(l, tm);
lc->update(pos, val);
} else {
if(!rc) this->rc = new Node(tm+1, r);
rc->update(pos, val);
}
}
ll query(ll tl, ll tr) {
if(tl > r || l > tr) return 0;
if(r <= tr && l >= tl) return this->sum;
ll res = 0;
if(lc) res += lc->query(tl,tr);
if(rc) res += rc->query(tl,tr);
return res;
}
};
Node *root;
bool check() {
ll curr = 1;
ll sum = root->sum;
while(sum > curr) {
ll res = root->query(1, curr);
if(res < curr) return false;
curr = res + 1;
}
return true;
}
bool init(int coinsCount, ll maxCoinSize, ll coins[]) {
root = new Node(1, maxCoinSize);
for(int i=0; i<coinsCount; i++)
root->update(coins[i], coins[i]);
return check();
}
bool is_happy(int event, int coinsCount, ll coins[]) {
for(int i=0; i<coinsCount; i++)
root->update(coins[i], coins[i] * event);
return check();
}
