#include <bits/stdc++.h>
#include "happiness.h"
using namespace std;
typedef long long ll;
const ll MAX_VAL = 1e12;
const ll INF = 2e18; // Giá trị cực tiểu để reset diff
struct Node {
ll sum = 0;
ll diff = -INF;
Node *l = nullptr, *r = nullptr;
void update(ll L, ll R) {
ll sum_l = (l ? l->sum : 0);
ll diff_l = (l ? l->diff : -INF);
ll diff_r = (r ? r->diff : -INF);
sum = sum_l + (r ? r->sum : 0);
// Công thức: Gap lớn nhất = max(Gap bên trái, Gap bên phải trừ đi tổng bên trái)
diff = max(diff_l, diff_r - sum_l);
}
};
Node* root = new Node();
void update_tree(Node* cur, ll l, ll r, ll x, int val) {
if (l == r) {
cur->sum += (ll)x * val;
// Nếu không còn tờ tiền nào ở mệnh giá này, diff phải biến mất (-INF)
cur->diff = (cur->sum > 0 ? x : -INF);
return;
}
ll mid = l + (r - l) / 2;
if (x <= mid) {
if (!cur->l) cur->l = new Node();
update_tree(cur->l, l, mid, x, val);
} else {
if (!cur->r) cur->r = new Node();
update_tree(cur->r, mid + 1, r, x, val);
}
cur->update(l, r);
}
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
for (int i = 0; i < coinsCount; i++) {
update_tree(root, 1, MAX_VAL, coins[i], 1);
}
// Điều kiện hạnh phúc: Gap lớn nhất so với tổng tích lũy không quá 1
return root->diff <= 1;
}
bool is_happy(int event, int coinsCount, long long coins[]) {
for (int i = 0; i < coinsCount; i++) {
update_tree(root, 1, MAX_VAL, coins[i], event);
}
return root->diff <= 1;
}
