Why Im getting TLE for problem on BINARY SEARCH

problem:- link text

my solution:-link text

Why im getting TLE error,I think my logic is right. Now how can i optimise my solution.Plz explain me

Your solution seems correct to me, but I don’t think your approach is good enough for given constraint.I think, it’s a BIT-related problem.You have to think according to that.
Here is a good tutorial to get started with BIT.

Happy Coding!

1 Like


This shifting of array elements is bound to give you TLE. It makes complexity roughly O(NQ).

Only those who solved the problem can see your solution atm. Try to give the ideone link for others.

1 Like

my solution :- http://ideone.com/fKzVRp

@vijju123 so how to optimise my solution

This problem needs you to use apt data structure. Check ayushagg31 's answer. You need Binary Indexed Tree for this problem.