FLIPCOIN : Need help

help
,
1

Hello guys,
I recently learned Segment Trees and applied it to the question: FLIPCOIN.
I am getting TLE in my solution. Here is a link to my solution. Please tell me why am I getting TLE and how to remove it.
Thanks :slight_smile:

2

knowledge of segment tree is not enough to solve this,lazy propagation is also required.

1 Like
3

Thanks…Can you please point out my mistake in code?

4

For this question, you have to use Segment Tree with lazy propagation.

Your code uses a simple Segment Tree without lazy propagation and hence gets a TLE.

In lazy propagation we mark the nodes that needs to be updated, but update them only when required. This saves time and makes this approach faster.

The following link has a nice blog about Segment Trees with lazy propagation.

http://se7so.blogspot.in/2012/12/segment-trees-and-lazy-propagation.html

You can refer to my code for the solution in the following link.

https://www.codechef.com/viewsolution/8685653

1 Like
5

Thanks for the help :slight_smile: