Regarding SPOJ-KGSS

general
,
1

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?

2

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: F6UQE9 - Online C++ Compiler & Debugging Tool - Ideone.com

1 Like
3

Thanks.Solved :slight_smile: