#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 = 1;
Node *update(int64_t i, Node *x, int64_t a, int64_t b, int64_t t)
{
if (!x)
{
x = (Node *)calloc(1, sizeof *x);
x->min_prefix_sum = INT64_MAX / 2;
}
if (a + 1 == b)
{
x->sum += t * i;
x->min_prefix_sum = x->sum ? -i + 1 : INT64_MAX / 2;
return x;
}
if (i <= (a + b) >> 1)
{
x->left = update(i, x->left, a, (a + b) >> 1, t);
x->sum = x->left->sum + (x->right ? x->right->sum : 0);
x->min_prefix_sum = x->left->min_prefix_sum;
if (x->right)
x->min_prefix_sum = min(x->min_prefix_sum, x->left->sum + x->right->min_prefix_sum);
}
else
{
x->right = update(i, x->right, (a + b) >> 1, b, t);
x->sum = (x->left ? x->left->sum : 0) + x->right->sum;
if (x->left)
x->min_prefix_sum = min(x->left->min_prefix_sum, x->left->sum + x->right->min_prefix_sum);
else
x->min_prefix_sum = x->right->min_prefix_sum;
}
return x;
}
bool init(int n, long long m, long long coins[])
{
while (l < m)
l <<= 1;
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;
}
