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

Need help in problem 279C (Ladders)
Автор kipawa, история, 9 лет назад, По-английски

I was solving problem 279C (Ladders)
My logic is to create two arrays inc and dec
inc[i] contains the largest j, such that i<=j and the sequence from ai, ai+1, ..., aj is increasing.
dec[i] contains minimum j, such that i>=j and the sequence from aj, aj+1, ..., ai is decreasing.
Now the sequence l,r is ladder if inc[l-1]==dec[r-1] || inc[l-1]>=r-1 || dec[r-1]<=l-1 (I used 0 based indexing)
I am getting WA on test 20, please help me!
Solution Link
Thanks in advance!

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

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

Hey I have solved the problem and used a similar approach here. Although my array names are a bit confusing, I have commented what they mean.

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
  1. have 2 dp arrays say rt[100005] and lt[100005];
  2. rt[i] stores the highest index to the right of i such that arr[i....rt[i]] is non decreasing
  3. and lt[i] stores the smallest index such that arr[lt[i].....i] is non-increasing.
  4. you can do each of these in O(n)
  5. now for a given query a,b , if rt[a] >= lt[b] ... i,e. arr[a..........rt[a]] — >non-decreasing ..........arr[lt[b].......b] ->non-increasing means there is a ladder. Came from a friend of mine. Helped me.
→ Ответить