I am new to segment tree, and was solving KGSS on SPOJ, I can’t understand why is my code giving WA.

Problem Link - https://www.spoj.com/problems/KGSS/

My Solution - https://ghostbin.com/paste/ppo76

I am new to segment tree, and was solving KGSS on SPOJ, I can’t understand why is my code giving WA.

Problem Link - https://www.spoj.com/problems/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))

2 Likes