unt311's blog

By unt311, history, 3 years ago, In English

This is a very cool problem with a short simple problem statement. I am getting TLE for a O(n * (logn)^2) solution.

Please provide a solution, or give suggestions to improve my solution (using binary search and segment tree)

  • Vote: I like it
  • -11
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Iterate over the maximum. Using a monotonic stack, you can find the position of the previous position that has an element $$$\ge$$$ this element and the next position that has an element $$$\ge$$$ this element, and once you have this information, it's $$$O(1)$$$ for each position, so the final complexity is $$$O(n)$$$.

Code