#include "happiness.h"
#include <bits/stdc++.h>
using namespace std;
struct vertex {
vertex *left_child = nullptr, *right_child = nullptr;
int64_t sum = 0, minprefix = 0;
vertex() {}
~vertex() {
delete left_child;
delete right_child;
left_child = nullptr;
right_child = nullptr;
}
void extend() {
if (left_child == nullptr) left_child = new vertex;
if (right_child == nullptr) right_child = new vertex;
}
void extend_left() {
if (left_child == nullptr) left_child = new vertex;
}
void extend_right() {
if (right_child == nullptr) right_child = new vertex;
}
void up() {
if (left_child == nullptr && right_child == nullptr) {
sum = 0;
minprefix = 0;
} else if (left_child == nullptr) {
sum = right_child->sum;
minprefix = min(int64_t(0), right_child->minprefix);
} else if (right_child == nullptr) {
sum = left_child->sum;
minprefix = left_child->minprefix;
} else {
sum = left_child->sum + right_child->sum;
minprefix = min(left_child->minprefix, left_child->sum + right_child->minprefix);
}
}
};
vertex root;
int64_t MAXC;
map<int64_t, int> nho;
void upd(int64_t u, int64_t d, vertex *cur = &root, int64_t lo = 1, int64_t hi = MAXC) {
if (lo == hi) {
cur->sum += d;
cur->minprefix = cur->sum;
return;
}
int64_t mid = (lo + hi) >> 1LL;
if (u <= mid) {
cur->extend_left();
upd(u, d, cur->left_child, lo, mid);
} else {
cur->extend_right();
upd(u, d, cur->right_child, mid + 1, hi);
}
cur->up();
}
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
MAXC = maxCoinSize;
for (int i = 0; i < coinsCount; i++) {
int64_t val = coins[i];
if (!nho.count(val)) {
upd(val, -val);
if (val < MAXC) upd(val+1, val);
}
++nho[val];
}
for (int i = 0; i < coinsCount; i++) {
int64_t val = coins[i];
if (val < MAXC) upd(val+1, val);
}
return (root.minprefix >= -1);
}
bool is_happy(int event, int coinsCount, long long coins[]) {
for (int i = 0; i < coinsCount; i++) {
int64_t val = coins[i];
if (event == 1) {
if (!nho.count(val)) {
upd(val, -val);
if (val < MAXC) upd(val+1, val);
} else if (nho[val] == 0) {
upd(val, -val);
if (val < MAXC) upd(val+1, val);
}
++nho[val];
} else {
--nho[val];
if (nho[val] == 0) {
upd(val, val);
if (val < MAXC) upd(val+1, -val);
}
}
if (val < MAXC) upd(val+1, event * val);
}
return (root.minprefix >= -1);
}
