#include "happiness.h"
#include <map>
using namespace std;
struct Node {
Node* left = nullptr;
Node* right = nullptr;
long long sum = 0, count = 0;
};
Node* root = new Node();
const long long MAX = 1e12;
void update(Node*& node, long long l, long long r, long long pos, long long val, long long delta) {
if (!node) node = new Node();
node->sum += val;
node->count += delta;
if (l == r) return;
long long mid = (l + r) / 2;
if (pos <= mid) update(node->left, l, mid, pos, val, delta);
else update(node->right, mid + 1, r, pos, val, delta);
}
pair<long long, long long> query(Node* node, long long l, long long r, long long ql, long long qr) {
if (!node || l > qr || r < ql) return {0, 0};
if (ql <= l && r <= qr) return {node->sum, node->count};
long long mid = (l + r) / 2;
auto left = query(node->left, l, mid, ql, qr);
auto right = query(node->right, mid + 1, r, ql, qr);
return {left.first + right.first, left.second + right.second};
}
bool is_happy_now() {
long long reach = 0;
long long next = 1;
while (true) {
auto [s, c] = query(root, 1, MAX, next, reach + 1);
if (c == 0) break;
reach += s;
next = reach + 1;
if (reach > 1e18) break;
}
auto [total, _] = query(root, 1, MAX, 1, MAX);
return reach >= total;
}
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
root = new Node();
for (int i = 0; i < coinsCount; ++i) {
update(root, 1, MAX, coins[i], coins[i], 1);
}
return is_happy_now();
}
bool is_happy(int event, int coinsCount, long long coins[]) {
if (event == -1) {
for (int i = 0; i < coinsCount; ++i)
update(root, 1, MAX, coins[i], -coins[i], -1);
} else {
for (int i = 0; i < coinsCount; ++i)
update(root, 1, MAX, coins[i], coins[i], 1);
}
return is_happy_now();
}
