I solved this problem using segment tree. For querying the two maximum numbers in a range(i,j), I called the query() function twice with different ranges. I have checked for several test cases and it is giving the correct answer but its showing WA in the judge. Please tell me where I am doing wrong. Here is the source code and the link to the problem.
Link to the problem- http://www.spoj.com/problems/KGSS/ link to the implemented code- http://ideone.com/wvoF5a
Please help me and Thanks!!
You can answer the queries with only one query operation. By your code, the tree is built using the property of an RMQ tree, always looking for the largest numbers. You should store the largest two numbers inside an segment, instead of only the largest one. For this, try change your array of only one number to pair or a class/struct to store this values.
Your update function does not work properly . You have assumed that an element that is already a max element won't be updated to a low value . Take this testcase for an example: N = 2 array[1] = 2 array[2] = 3 After building your tree: mat[1] = 2 mat[2] = 1 mat[3] = 2
Now suppose update is called on the index 2 (that is update array[2] to 1) Now array[2] is updated to 1 Due to this mat[1] should be 1 But According to your code , mat[1] = 2 Hence your update function is wrong !