Help with SNAKEEAT

Here is my solution for the question Snake Eating . Im getting a TLE.Can someone help me

It is because you are taking O(n) per query and the expected complexity per query is O(log(n)).

In worst case, suppose all snakes are of equal length lets say K-1 then you will end up to find eater to be the last element of array and then you will have to come to half of the array from last to get answer the query i.e. O(n).

Any tips on how can i use binary search for each query? I can’t come up with a solution

Refer the editorial, you have to implement another binary search with the given criteria in the editorial. If you are unable to implement one then refer

@alexander86 solution :

It is very similar to the one in editorial except he has used prefix sum array instead of difference sum prefix.