#include <bits/stdc++.h>
#include "happiness.h"
using namespace std;
#define int long long
using pii = pair<int, int>;
#define read(a) for (auto &x : a) cin >> x
#define V vector
#define show(a) for (auto x : a) cout << x << " "; cout << endl;
const int ninf = numeric_limits<int>::max();
struct Node
{
int l, r, ct, m, lz, s;
Node *ln, *rn;
};
void fn(Node *n)
{
if (n == nullptr) return;
fn(n->ln);
fn(n->rn);
delete n;
}
void ur(Node *n, int x, int d)
{
// printf("in ur\n");
auto &[l, r, ct, m, lz, s, ln, rn] = *n;
// printf("unpacked %lld %lld %lld %lld %lld %lld %lld %lld\n", l, r, ct, m, lz, s, ln, rn);
if (x >= r) return;
if (x < l)
{
lz += x * d;
if (ct) m += x * d;
return;
}
assert(ln != nullptr);
ur(ln, x, d);
ur(rn, x, d);
m = ninf;
if (ln->ct) m = min(m, ln->m + lz);
if (rn->ct) m = min(m, rn->m + lz);
}
void up(Node *n, int x, int d)
{
// printf("in up\n");
auto &[l, r, ct, m, lz, s, ln, rn] = *n;
ct += d;
s += x * d;
if (l == r)
{
assert(l == x);
if (ct) m = lz - x;
else m = ninf;
return;
}
int mid = (l + r) / 2;
if (ln == nullptr)
{
assert(ct == d);
ln = new Node {l, mid, 0, ninf, 0, 0, nullptr, nullptr},
rn = new Node {mid + 1, r, 0, ninf, 0, 0, nullptr, nullptr};
}
if (x <= mid) up(ln, x, d);
else up(rn, x, d);
if (ct == 0)
{
assert(s == 0);
assert(ln->lz == rn->lz);
lz += ln->lz;
m = ninf;
fn(ln);
fn(rn);
ln = rn = nullptr;
}
else
{
m = ninf;
if (ln->ct) m = min(m, ln->m + lz);
if (rn->ct) m = min(m, rn->m + lz);
}
}
void showtree(Node *n, int level)
{
for (int i = 0; i < level; i ++) cout << ' ';
if (n == nullptr)
{
printf("[null]\n");
return;
}
auto &[l, r, ct, m, lz, s, ln, rn] = *n;
printf("[%lld, %lld], ct=%lld, s=%lld, lz=%lld, m=%lld\n", l, r, ct, s, lz, m);
showtree(ln, level+2);
showtree(rn, level+2);
}
Node *st;
int nn, mm;
bool init(signed n, int m, int coins[])
{
nn = n, mm = m;
st = new Node {0, m, 0, ninf, 0, 0, nullptr, nullptr};
sort(coins, coins + n);
for (int i = 0; i < n; )
{
// printf("in loop\n");
int v = coins[i++], ct = 1;
while (i < n && coins[i] == v)
{
// printf("in while loop\n");
i ++, ct ++;
}
up(st, v, ct);
ur(st, v, ct);
// printf("done updating\n");
}
// showtree(st, 0);
// printf("exiting init\n");
return st->m >= -1;
}
bool is_happy(signed ev, signed c, int coins[])
{
sort(coins, coins + c);
for (int i = 0; i < c; )
{
int v = coins[i++], ct = 1;
while (i < nn && coins[i] == v) i ++, ct ++;
if (ev == 1)
{
up(st, v, ct);
ur(st, v, ct);
}
else
{
ur(st, v, -ct);
up(st, v, -ct);
}
}
// showtree(st, 0);
return st->m >= -1;
}
// #define NMAX 200000
// #define QMAX 100000
// static signed N, Q;
// static long long M;
// static long long coins[NMAX], A[5];
// signed main()
// {
// signed i, d;
// long long max_code;
// scanf("%d%lld", &N, &M);
// for (i = 0; i < N; ++i) {
// scanf("%lld", &coins[i]);
// }
// if (init(N, M, coins))printf("1\n");
// else printf("0\n");
// scanf("%d", &Q);
// for (i = 0; i < Q; ++i) {
// signed ck, c;
// scanf("%d%d", &ck, &c);
// for (int j = 0; j < c; j++) {
// scanf("%lld", &A[j]);
// }
// if (is_happy(ck, c, A))printf("1\n");
// else printf("0\n");
// }
// return 0;
// }
