Getting TLE in SPOJ problem

Hello.I am trying to solve following problem at SPOJ : http://www.spoj.com/problems/HORRIBLE/

I am getting TLE at the first test case.If someone can help me to optimize my approach it will be a great help.

My solution Link: http://ideone.com/Hjzd7A

Let me know if anything is unclear in my solution.Thanks.

You have to use lazy propagation in your function preprocess1. You are actually updating all values in the range for query type 0 (consider a test case where all the C commands are “0 1 n 1”, and see), making it an O(C*N) code, thus getting TLE. By lazy propagation you can reduce complexity of each query of type 0 p q v to log(N).

3 Likes

Thanks for answering.I will try that.

//