#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 INF = 1e18;
ll M;
map<ll, int> MM;
struct Node
{
ll val, lazy;
Node *lc, *rc;
Node() : val(0), lazy(0) {}
};
void busy(Node *node, ll tl, ll tr)
{
if(node->lazy==0) return;
node->val+=node->lazy;
if(tl!=tr)
{
if(node->lc==NULL) node->lc=new Node();
node->lc->lazy+=node->lazy;
if(node->rc==NULL) node->rc=new Node();
node->rc->lazy+=node->lazy;
}
node->lazy=0;
}
void update(Node *node, ll tl, ll tr, ll l, ll r, ll k)
{
busy(node, tl, tr);
if(r<tl || tr<l) return;
if(l<=tl && tr<=r)
{
node->lazy+=k;
busy(node, tl, tr);
return;
}
ll mid=tl+tr>>1;
if(node->lc==NULL) node->lc=new Node();
if(node->rc==NULL) node->rc=new Node();
update(node->lc, tl, mid, l, r, k);
update(node->rc, mid+1, tr, l, r, k);
node->val=INF;
node->val=min(node->val, node->lc->val+node->lc->lazy);
node->val=min(node->val, node->rc->val+node->rc->lazy);
}
Node *root;
ll query()
{
return root->val+root->lazy;
}
void push(ll x)
{
update(root, 1, M, x+1, M, x);
MM[x]++;
if(MM[x]==1)
{
auto it=MM.find(x);
ll val=-x;
if(next(it)!=MM.end()) val+=next(it)->first;
update(root, 1, M, prev(it)->first+1, x, val);
}
}
void pop(ll x)
{
update(root, 1, M, x+1, M, -x);
MM[x]--;
if(MM[x]==0)
{
auto it=MM.find(x);
ll val=x;
if(next(it)!=MM.end()) val-=next(it)->first;
update(root, 1, M, prev(it)->first+1, x, val);
MM.erase(x);
}
}
bool init(int coinsCount, ll maxCoinSize, ll coins[])
{
M=maxCoinSize;
root=new Node();
MM[0];
for(int i=0; i<coinsCount; i++) push(coins[i]);
return query()>=-1;
}
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()>=-1;
}
