I used a simple approach but i’m having a hard time understanding why it didn’t work, my approach was:-
- Create two segment trees which returns the first index of the max height element and last index of the max height element in a given range.
- If b>c then use the tree which returns the first index of the max element in range c to b-1 inclusive. add the deliciousness of that index to ans and then update my b position to that index and again get the max height index in range c to b-1, do this while b!=c
- if b < c then use the tree which returns the last index of max height in range b+1 to c, add the deliciousness of that index to ans then update b with that index and repeat the same while b!=c.
Using this approach i tested many test cases and all worked fine but when i got WA i have no idea why i got WA and my second concern is TLE. If building the tree takes n time and querying it takes logn time, why did i get TLE. Can someone tell me whats wrong with the logic