Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Mucosolvan's blog

By Mucosolvan, history, 4 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.com/contest/279/submission/20043264

Thanks for help!

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

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