Warriors - WARRIORS

Problem Link

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

const long long N = 100005, INF = 2e9;
long long ans[N], d[N];
long long B[N];

int bsearch(int x, int n)
{
int low = 1;
int high = n;
int mid, res;
res = 0;

while(low <= high)
{
mid = (low + high) / 2;
if(ans[mid] <= x)
{
res = mid;
low = mid + 1;
}
else
{
high = mid - 1;
}
}

return res;
}

int main()
{
int t, n, q, x;
std::ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);

cin >> t;

B[0] = 1;
    for (int i = 1; i <= 60; i++)
        B[i] = B[i - 1] + B[i - 1];
while(t--)
{
cin >> n >> q;
long long a[n];
for(int i = 1; i <= n; i++)
{
cin >> a[i];
}

sort(a + 1, a + n + 1);

for(int i = 1; i <= n; i++)
{
if(d[i - 1] > a[i])
{
ans[i] = ans[i - 1];
d[i] = 2 * (d[i - 1] - a[i]);
if(d[i] > INF)
{
d[i] = INF;
}
continue;
}

if(i >= 35)
{
ans[i] = ans[i - 1] + 1;
d[i] = INF;
continue;
}

long long x = a[i] - d[i - 1];
long long y = B[i - 1];
long long z = x / y + 1;
ans[i] = ans[i - 1] + z;
d[i] = d[i - 1] + z * B[i - 1];
d[i] = 2 * (d[i] - a[i]);
if(d[i] > INF)
{
d[i] = INF;
}
}

while(q--)
{
cin >> x;
cout << bsearch(x, n) << endl;
}
}
}