#include <bits/stdc++.h>
#include "happiness.h"
using namespace std;
using i64 = long long;
template<typename T>
using vec = vector<T>;
struct Node{
i64 bas,son,ans,sum;
int cnt;
Node *l,*r;
Node(){
bas = son = ans = sum = cnt = 0;
l = r = nullptr;
}
};
struct SegTree{
i64 n;
Node* root;
void init(i64 n){
this->n = n;
root = new Node();
}
Node merge(Node *l,Node *r){
Node tmp; tmp.l = l; tmp.r = r;
if (l->cnt == 0 && r->cnt == 0) return tmp;
if (l->bas != 0) tmp.bas = l->bas;
else tmp.bas = r->bas;
if (r->son != 0) tmp.son = r->son;
else tmp.son = l->son;
tmp.sum = l->sum + r->sum;
tmp.cnt = l->cnt + r->cnt;
int left = l->ans + l->sum * (tmp.cnt-l->cnt);
int right = r->ans + r->sum * (tmp.cnt-l->cnt-r->cnt);
tmp.ans = left + right;
return tmp;
}
void update(Node* node,int s,int e,int i,int inc){
if (s == e){
node->cnt += inc;
node->sum = node->cnt * s;
node->ans = s * (node->cnt * node->cnt - (node->cnt * (node->cnt + 1) / 2));
if (node->cnt != 0) node->bas = node->son = s;
else node->bas = node->son = 0;
return;
}
int m = (s+e) / 2;
if (node->l == nullptr) node->l = new Node();
if (node->r == nullptr) node->r = new Node();
if (i <= m) update(node->l,s,m,i,inc);
else update(node->r,m+1,e,i,inc);
*node = merge(node->l,node->r);
}
void update(int i,int inc){update(root,1,n,i,inc); }
};
SegTree tree;
int m;
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
m = maxCoinSize;
tree.init(m);
for (int i = 0; i < coinsCount; i++){
tree.update(coins[i],1);
}
Node node = *tree.root;
return node.cnt-1+node.ans >= node.sum - node.bas;
}
bool is_happy(int event, int coinsCount, long long coins[]) {
for (int i = 0; i < coinsCount; i++){
tree.update(coins[i],event);
}
Node node = *tree.root;
return node.cnt-1+node.ans >= node.sum - node.bas;
}
