#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#include "happiness.h"
#include <bits/stdc++.h>
using namespace std;
struct Node {
// sum that is required such that the first element of the subarray is chosen
long long reqSum = 0;
// sum of all elements in the subarray
long long buildSum = 0;
// index of left and right children
int lIdx = -1, rIdx = -1;
};
const long long n=((long long)1LL)<<40;
Node n1;
vector<Node> seg;
int pt=0;
vector<int> st;
void init() {
seg.assign((int)1e7 + 2*(int)1e6,n1);
st.assign(100,0);
}
inline void combine(Node &ret, Node &l, Node &r) {
ret.buildSum = l.buildSum + r.buildSum;
ret.reqSum = l.reqSum;
if (r.buildSum != 0)
ret.reqSum = max(l.reqSum, r.reqSum - l.buildSum);
}
inline void gen(int x, bool two, long long f) {
if (seg[x].lIdx != -1) return;
seg[x].lIdx = ++pt;
if (two) {
seg[pt].reqSum = f-1;
}
seg[x].rIdx = ++pt;
if (two) {
seg[pt].reqSum = f;
}
}
inline void inc(long long i, long long v) {
int x=0;
long long lx = 0;
long long rx = n;
int pp=-1;
while (rx-lx!=1) {
st[++pp]=x;
gen(x,rx-lx==2,lx);
long long m=(lx+rx)>>1;
if (i<m) rx=m, x=seg[x].lIdx;
else lx=m, x=seg[x].rIdx;
}
seg[x].buildSum += v;
for (int i=pp;i>-1;--i)
combine(seg[st[i]], seg[seg[st[i]].lIdx], seg[seg[st[i]].rIdx]);
}
bool happy() {
return seg[0].reqSum < 1;
}
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
init();
for (int i=0;i<coinsCount;++i) {
inc(coins[i], coins[i]);
}
return happy();
}
bool is_happy(int event, int coinsCount, long long coins[]) {
if (event == -1) {
for (int i=0;i<coinsCount;++i) {
inc(coins[i], -coins[i]);
}
}
else {
for (int i=0;i<coinsCount;++i) {
inc(coins[i], coins[i]);
}
}
return happy();
}
