Getting TLE in SPOJ problem

general
,
1

Hello.I am trying to solve following problem at SPOJ : SPOJ.com - Problem 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: Hjzd7A - Online C Compiler & Debugging Tool - Ideone.com

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

2

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
3

Thanks for answering.I will try that.