Mucosolvan's blog

By Mucosolvan, history, 8 years ago, In English

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!

  • Vote: I like it
  • +3
  • Vote: I do not like it

| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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].