#include "biscuits.h"
#include <iostream>
struct Node {
Node *left, *right;
long long sum;
};
int c = 0;
Node buffer[50000];
Node* build(Node* node, __int128 l, __int128 r, __int128 lim) {
if(r <= lim || node->sum == 0) {
return node;
}
if(lim <= l) {
return &buffer[0];
}
__int128 mid = (l + r) / 2;
Node *cur = &buffer[c++];
cur->left = build(node->left, l, mid, lim);
cur->right = build(node->right, mid, r, lim);
cur->sum = cur->left->sum + cur->right->sum;
return cur;
}
long long count_tastiness(long long x, std::vector<long long> a) {
buffer[0].left = buffer[0].right = &buffer[0];
buffer[0].sum = 0;
c = 1;
buffer[1].left = buffer[1].right = &buffer[0];
buffer[1].sum = 1;
c = 2;
for(int i = 0; i < 64; i++) {
a.push_back(0);
}
Node* root = &buffer[1];
__int128 sum = 0;
for(int i = 0; i < (int) a.size(); i++) {
sum += ((__int128) a[i]) << i;
// sum <= (y + pot) * x
// floor(sum / x) <= y + pot
// floor(sum / x) - pot <= y
Node* cur = &buffer[c++];
cur->left = root;
__int128 pot = (__int128) 1 << i;
cur->right = build(root, 0, pot, sum / x - pot + 1);
cur->sum = cur->left->sum + cur->right->sum;
root = cur;
//std::cout << "after i " << i << " got ans " << root->sum << " lim was " << (long long) (sum / x - pot + 1) << '\n';
}
return root->sum;
}
