flip coin medium

I am trying to solve Flip coin problem in the medium section

as i figured out normal approach gets time limit exceeded
what approach/algorithm should i use to optimize the code pls help !!

my code : http://www.codechef.com/viewsolution/3623067

As there are numerous queries of the order of 10^5, you have to give the result of each query in at most O(log(N)) time. So as this problem is of type range update, range query the best approach to solve the problem of FLIPCOIN is by using Segment Trees. Its construction time if O(N*log(N)). and gives the results of range queries in O(log(N)). Read these two links if you are new to this concept :

http://sportcoder.com/segment-trees/

http://letuskode.blogspot.in/2013/01/segtrees.html

1 Like
//