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