#include <bits/stdc++.h>
#include "happiness.h"
using namespace std;
struct Node
{
Node *left, *right;
int64_t sum, min_prefix_sum;
};
Node *root;
int64_t l, m;
void check_children(Node *const x)
{
if (!x->left)
{
x->left = (Node *)calloc(1, sizeof *x->left);
x->left->min_prefix_sum = INT64_MAX / 2;
}
if (!x->right)
{
x->right = (Node *)calloc(1, sizeof *x->right);
x->right->min_prefix_sum = INT64_MAX / 2;
}
}
void combine(Node *const x)
{
x->sum = x->left->sum + x->right->sum;
x->min_prefix_sum = min(x->left->min_prefix_sum,
x->left->sum + x->right->min_prefix_sum);
}
void update(int64_t i, Node *const x, int64_t a, int64_t b, int64_t t)
{
if (a + 1 == b)
{
x->sum += t * i;
x->min_prefix_sum = x->sum ? -i + 1 : INT64_MAX / 2;
return;
}
check_children(x);
if (i <= (a + b) >> 1)
update(i, x->left, a, (a + b) >> 1, t);
else
update(i, x->right, (a + b) >> 1, b, t);
combine(x);
}
bool init(int n, long long m, long long coins[])
{
l = 1 << (32 - __builtin_clz(m));
root = (Node *)calloc(1, sizeof *root);
for (size_t i = 0; i < n; i++)
update(coins[i], root, 0, l, 1);
return root->min_prefix_sum >= 0;
}
bool is_happy(int event, int n, long long coins[])
{
for (size_t i = 0; i < n; i++)
update(coins[i], root, 0, l, event);
return root->min_prefix_sum >= 0;
}
