#include "happiness.h"
#include <set>
#include <algorithm>
using namespace std;
multiset<long long> banknotes;
long long totalSum = 0;
bool is_happy_now() {
if (banknotes.empty()) return true;
if (*banknotes.begin() != 1) return false;
long long reach = 0;
for (long long value : banknotes) {
if (value > reach + 1) return false;
reach += value;
// Early exit — няма нужда да проверяваме повече от totalSum
if (reach >= totalSum) break;
}
return true;
}
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
banknotes.clear();
totalSum = 0;
for (int i = 0; i < coinsCount; ++i) {
banknotes.insert(coins[i]);
totalSum += coins[i];
}
return is_happy_now();
}
bool is_happy(int event, int coinsCount, long long coins[]) {
if (event == -1) { // Purchase — remove
for (int i = 0; i < coinsCount; ++i) {
auto it = banknotes.find(coins[i]);
if (it != banknotes.end()) {
banknotes.erase(it);
totalSum -= coins[i];
}
}
} else if (event == 1) { // Wage — add
for (int i = 0; i < coinsCount; ++i) {
banknotes.insert(coins[i]);
totalSum += coins[i];
}
}
return is_happy_now();
}
