1742E - Scuza - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;

#define fastIO  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)

#define ll long long
#define max(a,b) (((b)>(a)) ? b : a )
#define min(a,b) (((a)<(b)) ? a : b)
#define endl "\n"
#define space " "

long long binarySearch(long long key, long long mouse[], long long s, long long e)
{
    while(s<=e)
    {
        ll mid=(s+e)/2;

        if (mouse[mid]==key)          
            return mid;
        else if (mouse[mid]>key)      
            e=mid-1;
        else                        
            s=mid+1;
    }
    return -1;

    //O(logn), O(1)
}

long long gcd(long long a, long long b)
{
    return b == 0 ? a : gcd(b, a % b);
    //O(log(min(a,b)), O(log(min(a,b))
}

long long LCM(ll a, ll b)
{
    return a*b/gcd(a,b);
}

//---------------------------------------------------------------------------------------------------//

void solve()
{
    
    ll n,q;
    
    cin>>n>>q;
    pair<ll,ll> arr[n]; //index of maximum step before current index
    pair<ll,ll> question[q];
    
    arr[0].second=0;
    for(ll i=0;i<n;i++)
    {
        int temp;
        cin>>temp;
        arr[i].first=temp;
        
        if (i-1>=0)
        {
            arr[i].second=arr[i-1].second;
            if(temp>arr[arr[i-1].second].first)
            {
                arr[i].second=i;
            }
        }
    }
    
    for(ll i=0;i<q;i++)
    {
        ll temp;
        cin>>temp;
        question[i].first=temp;
        question[i].second=i;

    }

    // for(ll i=0;i<q;i++)
    // {
        
    //     ll legsLength=question[i].first;
        
    //     ll currentHeight=0;
    //     for(ll j=0;j<n;j++)
    //     {
    //         if (legsLength<arr[j])
    //         {
    //             break;
    //         }
    //         currentHeight+=arr[j];
            
    //     }
    //     cout<<currentHeight<<space;
    // }
    // cout<<endl;


    sort(question, question+q);
    ll answer[q];
    
 
    
    ll legsLength=question[q-1].first;
    ll currentHeight=0;
    ll currentStepIndex=0;
    
    for(ll i=0;i<n;i++)
    {
        if (legsLength<arr[i].first)
            break;
        currentHeight+=arr[i].first;
        currentStepIndex=i;
    }

    answer[question[q-1].second]=currentHeight;

    ll maxStepIndexUntilNow=arr[currentStepIndex].second;
    for(ll i=q-2;i>=0;i--)
    {
        legsLength=question[i].first;

        if (legsLength==0)
        {
            answer[question[i].second]=0;
            continue;
        }
        if (currentStepIndex>=0)
            maxStepIndexUntilNow=arr[currentStepIndex].second;
        while(maxStepIndexUntilNow>=0 && legsLength<arr[maxStepIndexUntilNow].first)
        {
            while(currentStepIndex>=0 && currentStepIndex>=maxStepIndexUntilNow)
            {
                currentHeight=currentHeight-arr[currentStepIndex].first;
                currentStepIndex--;
            }
            if (currentStepIndex>=0)
                maxStepIndexUntilNow=arr[currentStepIndex].second;
            else
                maxStepIndexUntilNow=-1;
        }

        answer[question[i].second]=currentHeight;
    }


    for(ll i=0;i<q;i++)
    {
        cout<<answer[i]<<space;
    }
    cout<<endl;
    

}

int main()
{
    fastIO;
    ll t;
    cin>>t;
    while(t--)
    {
        
        solve();
        

    }
    return 0;
}