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

Автор Mucosolvan, история, 8 лет назад, По-английски

Hello!

My submission is getting WA on test 21, since there's no editorial I can't see the desired solution and I can't figure out where my mistake is.

Here is the link : http://codeforces.net/contest/279/submission/20043264

Thanks for help!

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

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

The approach I used is to define R[i] = how much to the right can I go from i so that the elements don't decrease and L[i] = how much to the left can I go from i so that the elements don't decrease. We can compute this in linear time. Then to answer a query, I simply check if R[l] >  = L[r].