Блог пользователя unt311

Автор unt311, история, 3 года назад, По-английски

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)

  • Проголосовать: нравится
  • -11
  • Проголосовать: не нравится

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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