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

Автор biranchi, история, 4 года назад, По-английски

Hello, codeforces I was doing D of ACL contest 2 today. Before diving into the issue I want to specify that I know the basic use of segment tree, like finding max range query and update. It seemed to me similar with LIS. After scratching some time, I came up with segment tree idea. Here I am writing about my idea.

  1. taking x as input
  2. Finding the maximum range query of x-k to x+k i.e. maxh
  3. updating the index of x with the value of maxh+1.
  4. Atlast finding maximum range query from 1 to n

I am pretty sure that this method should solve this problem but in the contest, submission gave 6 correct and 26 wrong results. I want to know your feedback and suggestions.

I copied the code of the segment tree from gfg and modified as per the requirements. Here is my code link Here is problem link

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

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

You're taking ranges of segtree as 1 to n where n is the length of the array. Range of segtree should be upto 3e5(max array element possible). Link to my submission.

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

size of segment tree is incorrect