#include "happiness.h"
typedef long long llong;
llong mx;
struct node {
int l, r;
llong sum;
node() : l(-1), r(-1), sum(0) {}
} ns[42 * 600000];
int _alloc() {
static int tp = 0;
return tp++;
}
void update(int &i, llong s, llong e, llong x, llong v) {
if (i == -1) i = _alloc();
ns[i].sum += v;
if (s == e) return;
llong m = (s + e) / 2;
if (x <= m) update(ns[i].l, s, m, x, v);
else update(ns[i].r, m + 1, e, x, v);
}
llong query(int &i, llong s, llong e, llong x) {
if (i == -1) return 0;
if (x < s) return 0;
if (e <= x) return ns[i].sum;
llong m = (s + e) / 2;
return query(ns[i].l, s, m, x) + query(ns[i].r, m + 1, e, x);
}
int rt;
bool check() {
llong sum = 0, pr = -1;
while (pr != sum) sum = query(rt, 1, mx, (pr = sum) + 1);
return sum == ns[rt].sum;
}
bool init(int coinsCount, llong maxCoinSize, llong coins[]) {
rt = _alloc();
mx = maxCoinSize;
for (int i = 0; i < coinsCount; ++i)
update(rt, 1, mx, coins[i], coins[i]);
return check();
}
bool is_happy(int event, int coinsCount, llong coins[]) {
for (int i = 0; i < coinsCount; ++i)
update(rt, 1, mx, coins[i], event * coins[i]);
return check();
}
