GOTHAM -SPYB21B

Can Someone please tell me how can I solve this. I got TLE when I did it…
here is my code -
https://www.codechef.com/viewsolution/45067794

Someone please explain to me… or add an editorial of this one.

U can use set in this problem , see we want to find the next location at which some capacity is there , So what we can do ? we fill all the indexes from 1 to N (and N+1 too ) in set (if u don’t know set in c++ then read ) , now for given index we have to find greater or equal to given index such that still some space is present , as set is sorted so we can easily use lower_bound (aka binary search) , now fill the value , if it completly fills then remove that index from set , for next index again do lower_bound with previous index -

lli n;
    cin>>n;
    lli a[n+1];
    seti st;
    FOR(i,1,n+1){
        cin>>a[i];
        st.insert(i);
    }
    st.insert(n+1);
    lli q;
    cin>>q;
    while(q--)
    {
        lli x,people;
        cin>>x>>people;
        lli i  = *st.lower_bound(x);
        lli ans = 0;
        while(people!=0 and i!=(n+1) ) // if i==n+1 means we exceed the limit so all will be die
        {
            lli prev = i;
            if(a[i]>0) //means some capacity is remaining
            {
                if(a[i]>people){
                    a[i]-=people;
                    ans += (i-x)*people;
                    people = 0;
                    break;
                }
                else
                    {
                        people-=a[i];
                        ans+=(i-x)*a[i];
                        a[i] = 0;
                        st.erase(i); //bcz if the capacity of i'th box is zero then we have to remove
                    }
            }
             i  = *st.lower_bound(prev); 
        }
        print(ans);
    }
1 Like