hardy_9795's blog

Help needed in atcoder problem.
By hardy_9795, history, 4 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Someone please help.

→ Reply
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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.

→ Reply