Contest Page | CodeChef here the link to the question.
so here’s what I did…for each query I calculated for R and then for L and the difference of both is what I got as an answer. for each query, it is taking O(4*n) =~ O(n). but this only fetches me 25 points.
here’s the link to code Pp9YtZ - Online C++0x Compiler & Debugging Tool - Ideone.com
you said for each query O(n) and there are q queries so, O(qn) which didn’t pass! so, what was wrong here?
Wow! That sounds fishy. I observed your code. Your solution takes exactly O(n * Q), so forcedly it fetched ya 25 points.
Ya gotta read author’s solutions in codechef’s discussion. Tryna use BIT and heap to solve it again! Good luck to ya.