#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 = 0; bool len_one = false; NODE *left = nullptr, *right = nullptr; }; NODE *root = new NODE(); ll n; NODE merge(NODE a, NODE b) { NODE res; res.sum = a.sum + b.sum; res.diff = max( (a.len_one == true ? 0 : a.diff), b.diff - a.sum); return res; } void push(NODE *cur) { if (!cur->left) cur->left = new NODE(); if (!cur->right) cur->right = new NODE(); } void update(NODE *cur, ll l, ll r, ll x , int val) { if (l == r) { cur->sum += x * val; cur->diff = x; cur->len_one = true; return; } push(cur); ll mid = l + r >> 1; if (x <= mid) update(cur->left, l, mid, x , val); else update(cur->right, mid + 1, r, x , val); NODE res = merge(*(cur->left), *(cur->right)); cur->sum = res.sum; cur->diff = res.diff; } NODE get(NODE *cur, ll l, ll r, ll u, ll v) { if (u <= l && r <= v) return *cur; ll mid = l + r >> 1; push(cur); if (v <= mid) return get(cur->left, l, mid, u, v); if (u > mid) return get(cur->right, mid + 1, r, u, v); return merge(get(cur->left, l, mid, u, v), get(cur->right, mid + 1, r, u, v)); } public: SegmentTree(ll n) : n(n) {} void upd(ll pos , int val) { update(root, 1, n, pos, val); } bool query(ll u, ll v) { NODE res = get(root, 1, n, u, v); return (res.len_one == true || res.diff <= 1); } }st(N + 1); ll sum = 0; int cnt1 = 0; bool init(int coinsCount, long long maxCoinSize, long long coins[]){ FOR(i,0,coinsCount - 1){ st.upd(coins[i] , 1); sum += coins[i]; if(coins[i] == 1) cnt1 ++; } return (cnt1 && st.query(1 , sum)); } bool is_happy(int event, int coinsCount, long long coins[]){ if(event == 1){ FOR(i,0,coinsCount - 1){ ll x = coins[i]; st.upd(x , 1); sum += x; if(x == 1) cnt1 ++; } return (cnt1 && st.query(1 , sum)) ; } else{ FOR(i, 0 , coinsCount - 1){ ll x = coins[i]; st.upd(x , - 1); sum -= x; if(x == 1) cnt1 --; } return (cnt1 && st.query(1 , sum)) ; } }