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.
- taking x as input
- Finding the maximum range query of x-k to x+k i.e. maxh
- updating the index of x with the value of maxh+1.
- 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.