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

Help needed in atcoder problem.
Автор hardy_9795, история, 4 года назад, По-английски

Please help me in solving this problem. There is no editorial available for this problem.

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

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

Someone please help.

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

It is solved with segment tree. You go through the array and keep the segment tree where for every number you store the length of the longest such sequence that ends on such number. When you handle new array element, you just have to take maximum on [a[i] — k, a[i] + k] plus one and update the value for a[i] in the segment tree.

→ Ответить