AtCoder Beginner Contest 408 F

https://atcoder.jp/contests/abc408/tasks/abc408_f

DPを低いほうから行います。入力例1で、最初は1で最大回数は0です。次の2も0です。次の3の前に2以上高さが違っていればいいので、1に0をセットして、そして3の前後1の範囲で最大値を求めて1を足したものが3での最大回数です。
このように範囲で最大値を得られるような木を作ればよいです。あと木に値を入れるのはDだけ遅らせます。

// Athletic
#![allow(non_snake_case)]

use std::cmp::max;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// Segment Tree ////////////////////

type Val = i32;
type Range = (usize, usize);

struct SegmentTree {
    n: usize,
    v: Vec<Val>,
}

impl SegmentTree {
    fn max(&self, rng: Range) -> Val {
        self.max_core(rng, 0, self.n, 0)
    }
    
    fn max_core(&self, rng: Range, first: usize, last: usize, i: usize) -> Val {
        if rng.0 <= first && last <= rng.1 {
            self.v[i]
        }
        else {
            let mid = (first + last) / 2;
            if rng.1 <= mid {
                self.max_core(rng, first, mid, i*2+1)
            }
            else if rng.0 >= mid {
                self.max_core(rng, mid, last, i*2+2)
            }
            else {
                max(self.max_core(rng, first, mid, i*2+1),
                    self.max_core(rng, mid, last, i*2+2))
            }
        }
    }
    
    fn update(&mut self, i: usize, a: Val) {
        self.update_core(self.n - 1 + i, a)
    }
    
    fn update_core(&mut self, i: usize, a: Val) {
        if i < self.n - 1 {
            self.v[i] = max(self.v[i*2+1], self.v[i*2+2])
        }
        else {
            self.v[i] = a
        }
        
        if i > 0 {
            self.update_core((i - 1) / 2, a)
        }
    }
    
    fn ceil_two_pow(n: usize) -> usize {
        if n == 1 { 1 } else { SegmentTree::ceil_two_pow((n+1)/2) * 2 }
    }
    
    fn create(m: usize) -> SegmentTree {
        let n = SegmentTree::ceil_two_pow(m);
        let v: Vec<Val> = vec![-1; n*2-1];
        SegmentTree { n, v }
    }
}


//////////////////// process ////////////////////

type Height = usize;

fn read_input() -> (Height, usize, Vec<Height>) {
    let v: Vec<usize> = read_vec();
    let (_N, D, R) = (v[0], v[1] as Height, v[2]);
    let H: Vec<Height> = read_vec();
    (D, R, H)
}

fn sort_positions(a: &Vec<Height>) -> Vec<usize> {
    let mut b: Vec<(Height, usize)> = a.iter().cloned().zip(0..).collect();
    b.sort();
    b.into_iter().map(|(_, i)| i).collect::<Vec<_>>()
}

fn F(D: Height, R: usize, H: Vec<Height>) -> Val {
    let N = H.len();
    let mut dp: Vec<Val> = vec![0; N];
    let mut tree = SegmentTree::create(N);
    let ps = sort_positions(&H);
    for i in 0..N {
        let p = ps[i];
        if i >= D {
            tree.update(ps[i-D], dp[ps[i-D]])
        }
        let first = if p < R { 0 } else { p - R };
        let last = if p + R < N { p + R + 1 } else { N };
        dp[ps[i]] = tree.max((first, last)) + 1
    }
    dp.into_iter().max().unwrap()
}

fn main() {
    let (D, R, H) = read_input();
    println!("{}", F(D, R, H))
}