#include "happiness.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Tree
{
int sz = 1;
struct node
{
ll val, l, r;
int rc, lc;
}null = { 0, 0, 0, 0, 0 };
vector<node>t;
void init(ll m)
{
t.assign(sz + 1, null);
t[1].l = 1;
t[1].r = m;
}
void add_node(ll new_l, ll new_r)
{
sz++;
t.push_back({ 0, new_l, new_r, 0, 0 });
}
void update(int x, ll lx, ll rx, ll pos, ll val)
{
if (pos > rx || pos < lx)return;
if (lx == rx) {
t[x].val += val;
return;
}
ll mid = (lx + rx) / 2ll;
if (t[x].lc == 0)
{
add_node(lx, mid);
t[x].lc = sz;
}
if (t[x].rc == 0)
{
add_node(mid + 1ll, rx);
t[x].rc = sz;
}
update(t[x].lc, lx, mid, pos, val);
update(t[x].rc, mid + 1ll, rx, pos, val);
t[x].val = t[t[x].lc].val + t[t[x].rc].val;
}
ll qry(int x, ll lx, ll rx, ll l, ll r)
{
if (lx > r || rx < l)
return 0ll;
if (lx >= l && rx <= r) {
return t[x].val;
}
ll mid = (lx + rx) / 2ll;
if (t[x].lc == 0)
{
add_node(lx, mid);
t[x].lc = sz;
}
if (t[x].rc == 0)
{
add_node(mid + 1ll, rx);
t[x].rc = sz;
}
return qry(t[x].lc, lx, mid, l, r) +
qry(t[x].rc, mid + 1, rx, l, r);
}
}segTree;
ll all_sum;
bool ans()
{
ll ind = 1, sm = all_sum;
while (ind <= sm)
{
ll indx = segTree.qry(1, 1, segTree.t[1].r, 1, ind);
if (indx < ind)return false;
ind = indx + 1;
}
return true;
}
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
segTree.init(maxCoinSize);
for (int i = 0; i < coinsCount; i++)
{
segTree.update(1, 1, maxCoinSize, coins[i], coins[i]);
all_sum += coins[i];
}
return ans();
}
bool is_happy(int event, int coinsCount, long long coins[])
{
for (int i = 0; i < coinsCount; i++)
{
segTree.update(1, 1, segTree.t[1].r, coins[i], event * coins[i]);
all_sum += event * coins[i];
}
return ans();
}
