TLE in MULTQ3

codechef
lazy
multq3
segment-tree
segment-trees
spoj
tle

#1

I am getting TLE in MULTQ3.

Here is my code, please help.

I have used segment trees with lazy propagation. I have also used fast I/O, still I am getting TLE.

Please Help, I am stuck from very long time.


#2

the time limit is a tad too strict :wink: . In your code,I shortened the length of the tree from 8x10^6 to 3x10^5, made the tree from static to global, and removed the tree as a parameter from all the functions, and the same code gets AC
Here’s the AC submission: http://www.codechef.com/viewsolution/5577407
try to avoid allocating extra space, and adding unnecessary parameters to functions wherever possible :slight_smile:
I appreciate you in writing such a clean and precise code… really helped in debugging


#3

Getting TLE. Used lazy propagation. Is there any problem with my implementation of lazy ?

Code : http://www.codechef.com/viewsolution/7075422


#4

Thank you very much, I was stuck in many problems of lazy propagation and was on the verge on convincing myself that my implementation of lazy update is wrong.You have helped me very much.Thank you once again @gvaibhav21.


#5

you’re welcome :slight_smile: