#include "happiness.h"
#include <vector>
#include <iostream>
using namespace std;
struct Node {
int left = 0, right = 0;
long long count = 0;
};
const long long MAX_VAL = 1e12;
vector<Node> tree(2);
int next_id = 2;
void update(int node, long long l, long long r, long long pos, int diff) {
if (l == r) {
tree[node].count += diff;
return;
}
long long mid = (l + r) / 2;
if (pos <= mid) {
if (!tree[node].left) {
tree[node].left = next_id++;
if (tree.size() <= next_id) tree.resize(next_id + 5);
}
update(tree[node].left, l, mid, pos, diff);
} else {
if (!tree[node].right) {
tree[node].right = next_id++;
if (tree.size() <= next_id) tree.resize(next_id + 5);
}
update(tree[node].right, mid + 1, r, pos, diff);
}
tree[node].count = 0;
if (tree[node].left) tree[node].count += tree[tree[node].left].count;
if (tree[node].right) tree[node].count += tree[tree[node].right].count;
}
bool dfs_check(int node, long long l, long long r, long long &reach) {
if (!node) return true;
if (l == r) {
if (l > reach + 1 && tree[node].count > 0)
return false;
reach += tree[node].count * l;
if (reach >= 1e18) reach = 1e18;
return true;
}
long long mid = (l + r) / 2;
if (!dfs_check(tree[node].left, l, mid, reach)) return false;
if (!dfs_check(tree[node].right, mid + 1, r, reach)) return false;
return true;
}
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
tree = vector<Node>(2);
next_id = 2;
for (int i = 0; i < coinsCount; ++i)
update(1, 1, MAX_VAL, coins[i], 1);
long long reach = 0;
return dfs_check(1, 1, MAX_VAL, reach);
}
bool is_happy(int event, int coinsCount, long long coins[]) {
for (int i = 0; i < coinsCount; ++i) {
if (event == 1) {
update(1, 1, MAX_VAL, coins[i], 1);
} else {
update(1, 1, MAX_VAL, coins[i], -1);
}
}
long long reach = 0;
return dfs_check(1, 1, MAX_VAL, reach);
}
