#include <bits/stdc++.h>
#include "happiness.h"
using namespace std;
using ll = long long;
struct node {
int left, right;
ll sum, bound;
void apply(ll x) {
sum += x;
bound = sum - 1;
}
void merge(node &l, node &r) {
bound = max(l.bound, r.bound - l.sum);
sum = l.sum + r.sum;
}
};
class sparseseg {
public:
vector<node> a;
sparseseg() : a() {
a.reserve(100000);
a.push_back({-1, -1, 0, 0});
}
void push(int x) {
// cout << "push " << x << endl;
if (a[x].left == -1) {
a[x].left = a.size();
a.push_back({-1, -1, 0, 0});
}
if (a[x].right == -1) {
a[x].right = a.size();
a.push_back({-1, -1, 0, 0});
}
}
void upd(ll lll, ll rr, ll l, ll r, int v, ll x) {
if (r < lll || rr < l) return;
else if (lll <= l && r <= rr) a[v].apply(x);
else {
push(v);
ll m = (l + r) / 2;
upd(lll, rr, l, m, a[v].left, x);
upd(lll, rr, m + 1, r, a[v].right, x);
a[v].merge(a[a[v].left], a[a[v].right]);
}
}
};
sparseseg tree;
node get;
const ll bound = ll(1000000) * 1000000 + 1;
bool init(int coinsCount, ll maxCoinSize, ll coins[]) {
for (int i = 0; i < coinsCount; i++) tree.upd(coins[i], coins[i], 0, bound, 0, coins[i]);
// cout << "bound " << tree.a[0].bound << " " << tree.a.size() << endl;
return tree.a[0].bound <= 0;
}
bool is_happy(int event, int coinsCount, ll coins[]) {
for (int i = 0; i < coinsCount; i++) tree.upd(coins[i], coins[i], 0, bound, 0, event * coins[i]);
// cout << "bound " << tree.a[0].bound << endl;
return tree.a[0].bound <= 0;
}
