#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; }