#include "happiness.h"
struct Node {
long long l, r, sum;
Node* lc, * rc;
Node(long long l, long long r) : l(l), r(r), sum(0), lc(nullptr), rc(nullptr) {}
void update(long long p, long long v) {
sum += v;
if (l != r) {
int mid = (l + r) / 2;
if (p <= mid) {
if (lc == nullptr)
lc = new Node(l, mid);
lc->update(p, v);
}
else {
if (rc == nullptr)
rc = new Node(mid + 1, r);
rc->update(p, v);
}
}
}
long long query(long long a, long long b) {
if (l >= a && r <= b)
return sum;
int mid = (l + r) / 2;
long long total = 0;
if (a <= mid && lc != nullptr)
total += lc->query(a, b);
if (b >= mid + 1 && rc != nullptr)
total += rc->query(a, b);
return total;
}
};
Node* root;
bool check() {
long long curr = 1, sum = root->sum;
while (curr < sum) {
long long t = root->query(1, curr);
if (t < curr)
return false;
curr = t + 1;
}
return true;
}
bool init(int coinsCount, long long maxCoinSize, long long 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, long long coins[]) {
for (int i = 0; i < coinsCount; i++)
root->update(coins[i], event * coins[i]);
return check();
}
