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