Thank you for your videos. I think it will be great if you do some hard problems or problems based on some rare topic 
Keep up the good work!
Hi @ista2000,
Thanks for the feedback!
There are some hard and rare problems picked up on the channel: Mo’s Algorithm with Updates, Fourier Transform, Persistent Segment Trees etc…
You could have a look at them.
1 Like
I haven taken a different approach to solve the problem, the idea:
for each number of eaten snakes compute the length of the smallest remaining snake and store it in an array.
All what needs to be done for a query k is to binary search that array for the fist entry >= k and return n-index.
When submitting the solution I encountered the following strange behaviour:
I get a TLE for the original solution (see my solution).
I produced a WA “on purpose” by not considering the last query in the last testcase (see without last query). BUT I get the WA at a time of 0.23 seconds - hence pretty fast. I came to the last solution but optimizing my first one through many steps and the time when I got the WA on purpose constantly decreased (started with 3 seconds and went through 0.99, 0.3 til 0.23).
Can anyone explain this behavior to me? I can’t imagine a single query causing the time difference from 0.23 to TLE. Am I missing something? Or are the times for WA not representative? But somehow they are, because times decreased as I optimized my solution.
Would be glad for any ideas which give some insight on this!
What is presum[0]?
can somebody give me some inputs on online and offline solutions?
I have sorted array outside the query loop and used only binary search inside, can someone tell me why I am getting TLE? link to my code: https://www.codechef.com/viewsolution/17657932