Regarding SPOJ-KGSS

Problem :SPOJ-KGSS

My approach: I have implemented a segment tree for finding max in [l,r]. Whenever any query is asked I find out the maximum element in [l,r] and then update the segment tree by replacing the maximum element found by -INF.Now, I find out the maximum element which gives me the second largest element in [l,r].At last, I update the first largest back to its initial value.
My code:

I am getting TLE. How can I optimize the updation part?

I solved this using the same approach.

A single update function should work. Instead of storing the maximum value, you can store the index of the maximum value, or both.

Here: http://ideone.com/F6UQE9

1 Like

Thanks.Solved :slight_smile: