#include "happiness.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll MAXN = 1e18;
const int MAXVAL = 8e6;
ll M;
struct Node
{
ll val;
int lc, rc;
Node() : val(0), lc(-1), rc(-1) {}
};
Node nodes[MAXVAL];
int ncnt, root;
int newNode() { return ncnt++; }
void update(int node, ll tl, ll tr, ll p, ll k)
{
nodes[node].val+=k;
if(tl==tr) return;
ll mid=tl+tr>>1;
if(p<=mid)
{
if(nodes[node].lc==-1) nodes[node].lc=newNode();
update(nodes[node].lc, tl, mid, p, k);
}
else
{
if(nodes[node].rc==-1) nodes[node].rc=newNode();
update(nodes[node].rc, mid+1, tr, p, k);
}
}
ll query(int node, ll tl, ll tr, ll l, ll r)
{
if(r<tl || tr<l) return 0;
if(l<=tl && tr<=r) return nodes[node].val;
ll mid=tl+tr>>1;
ll ret=0;
if(nodes[node].lc!=-1) ret+=query(nodes[node].lc, tl, mid, l, r);
if(nodes[node].rc!=-1) ret+=query(nodes[node].rc, mid+1, tr, l, r);
return ret;
}
void push(ll x)
{
update(root, 1, M, x, x);
}
void pop(ll x)
{
update(root, 1, M, x, -x);
}
bool query()
{
ll now=1;
ll sum=query(root, 1, M, 1, M);
while(now<sum)
{
ll t=query(root, 1, M, 1, now);
if(t<now) return 0;
now=t+1;
}
return 1;
}
bool init(int coinsCount, ll maxCoinSize, ll coins[])
{
M=maxCoinSize;
root=newNode();
for(int i=0; i<coinsCount; i++) push(coins[i]);
return query();
}
bool is_happy(int event, int coinsCount, ll coins[])
{
if(event==-1) for(int i=0; i<coinsCount; i++) pop(coins[i]);
else for(int i=0; i<coinsCount; i++) push(coins[i]);
return query();
}
