I am new to segment tree, and was solving KGSS on SPOJ, I can’t understand why is my code giving WA.
Problem Link - SPOJ.com - Problem KGSS
My Solution - https://ghostbin.com/paste/ppo76
The equation you are using to get the second maximum is not correct.
Consider the example where left child (A) of segment tree is having the dual(8, 2) and right child (B) is having the dual(6, 4).
Now according to your equation the second maximum would be min(max(8, 6), max(2, 4)) = 4 but the second maximum is 6.
The correct equation would be max(min(A.first, B.first), max(A.second, B.second))
3 Likes