#include <bits/stdc++.h> #include <cstdlib> #include "happiness.h" #define endl '\n' #define fi first #define se second #define eb emplace_back #define pb push_back #define ce cout << endl #define ALL(A) A.begin(), A.end() #define FOR(i, l, r) for (int i = l; i <= r; i++) #define FOR2(i, l, r) for (int i = l; i >= r; i--) using namespace std; using ll = long long; using pll = pair<ll, ll>; using pii = pair<int, int>; using str = string; using ull = unsigned long long; using ld = long double; const ll INF = 1e18; const ll N = 1e12; const int LOGN = 14; const int C = 2000; const int heavy = 500; const int MOD = 1e9 + 7; const int Q = 50000; int dx[] = {0, 1, 0, -1}; // east, south, west, north int dy[] = {1, 0, -1, 0}; // T_Danh - Tri An High School struct SegmentTree { private: struct NODE { ll sum = 0; ll diff = -INF; NODE *left = nullptr, *right = nullptr; NODE() {} }; NODE *root = new NODE(); void pull(NODE *cur) { ll sum_l = (cur->left ? cur->left->sum : 0); ll diff_l = (cur->left ? cur->left->diff : -INF); ll diff_r = (cur->right ? cur->right->diff : -INF); cur->sum = sum_l + (cur->right ? cur->right->sum : 0); cur->diff = max(diff_l, diff_r - sum_l); } public: void update(NODE *&cur, ll l, ll r, ll x, int val) { if (!cur) cur = new NODE(); if (l == r) { cur->sum += (ll)x * val; cur->diff = (cur->sum > 0 ? x : -INF); return; } ll mid = l + (r - l) / 2; if (x <= mid) update(cur->left, l, mid, x, val); else update(cur->right, mid + 1, r, x, val); pull(cur); } bool is_happy() { return root->diff <= 1; } NODE*& get_root() { return root; } }; SegmentTree st; bool init(int coinsCount, long long maxCoinSize, long long coins[]) { for (int i = 0; i < coinsCount; i++) { st.update(st.get_root(), 1, N, coins[i], 1); } return st.is_happy(); } bool is_happy(int event, int coinsCount, long long coins[]) { for (int i = 0; i < coinsCount; i++) { st.update(st.get_root(), 1, N, coins[i], event); } return st.is_happy(); }