#include "happiness.h"
//Dost SEFEROĞLU
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<
#define vi vector<int>
#define all(xx) xx.begin(),xx.end()
const int inf = 1e18;
int LIM;
struct Node {
int sm=0,mn=inf;
Node *l,*r;
} *root = new Node;
pii cmp(const pii& p1,const pii& p2) {
if (p1.ff == inf) return p2;
if (p2.ff == inf) return p1;
return (p1.second < p2.second)?p1:p2;
}
void prop(Node* node,int l,int r,int p,int v) {
if (l == r) {
node->sm+= v*p;
node->mn = node->sm ? -p+1 : inf;
return;
}
int m = (l+r) >> 1;
if (p <= m) {
if (!node->l) node->l = new Node;
prop(node->l,l,m,p,v);
node->sm = node->l->sm+(node->r?node->r->sm:0);
node->mn = node->l->mn;
if (node->r) node->mn = min(node->mn,node->l->sm+node->r->mn);
}
else {
if (!node->r) node->r = new Node;
prop(node->r,m+1,r,p,v);
node->sm = node->r->sm+(node->l?node->l->sm:0);
node->mn = (node->l?node->l->sm:0)+node->r->mn;
if (node->l) node->mn = min(node->mn,node->l->mn);
}
}
bool init(int32_t coinsCount, long long maxCoinSize, long long coins[]) {
LIM = maxCoinSize;
for (int i=0;i<coinsCount;i++) prop(root,1,LIM,coins[i],1);
return root->mn >= 0;
}
bool is_happy(int32_t event, int32_t coinsCount, long long coins[]) {
for (int i=0;i<coinsCount;i++) prop(root,1,LIM,coins[i],event);
return root->mn>=0;
}
