#include "happiness.h"
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef pair<ll,ll> pll;
typedef vector<string> vs;
typedef vector<pll> vpl;
typedef vector<int> vi;
const ll inf = 1e16;
const ll MAX = (1e12) + 10;
struct node{
node* c[2];
ll sum;
node(){c[0] = c[1] = nullptr;sum = 0;}
void upd(ll p,ll v,ll i = 0, ll j = MAX){
if(i == j){
sum+=v;
return;
}
ll m = (i + j)/2;
if(p<=m){
if(!c[0])c[0] = new node();
c[0]->upd(p,v,i,m);
}else{
if(!c[1])c[1] = new node();
c[1]->upd(p,v,m+1,j);
}
sum=(c[0] ? c[0]->sum : 0) + (c[1] ? c[1]->sum : 0);
}
ll query(ll a,ll b,ll i = 0,ll j = MAX){
if(i > j || i > b || j < a)return 0;
if(a<=i and j<=b)return sum;
ll m = (i + j)/2;
return (c[0] ? c[0]->query(a,b,i,m) : 0) + (c[1] ? c[1]->query(a,b,m+1,j) : 0);
}
};
node* tree;
ll tot=0;
ll mx = 0;
bool good(){
ll have = 0;
while(have < min(mx,tot)){
ll novo = tree->query(0,have + 1);
if(novo == have)return 0;
have = novo;
}
return 1;
}
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
tree = new node();
mx = maxCoinSize;
tot=0;
for(int i=0;i<coinsCount;i++){
ll v = coins[i];
tree->upd(v,v);
tot+=v;
}
return good();
}
bool is_happy(int event, int coinsCount, long long coins[]) {
for(int i=0;i<coinsCount;i++){
ll v = coins[i];
tree->upd(v,v*event);
tot+=v*event;
}
return good();
}
