AtCoder Beginner Contest 336 D

https://atcoder.jp/contests/abc336/tasks/abc336_d

左から見て、その位置からどこまでがピークになり得るかを調べます。右からも同様です。
入力例1だとそれぞれ0-basedで、

2 2 2 3 4
0 0 1 2 4

そして、上の左から見ていって、2以下で一番右の場所を探します。そうすると、index: 3が2になります。長さは4ですが、ピラミッドは奇数なので長さ3で、サイズは2です。つまり、ある数以下で最も右の位置を探せばよいです。

// Pyramid
#![allow(non_snake_case)]

use std::cmp::{min, 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 ////////////////////

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

impl SegmentTree {
    fn ceil_two_pow(n: usize) -> usize {
        if n == 1 { 1 } else { SegmentTree::ceil_two_pow((n+1)/2) * 2 }
    }
    
    fn create(B: Vec<usize>) -> SegmentTree {
        let m = B.len();
        let n = SegmentTree::ceil_two_pow(m);
        let mut v: Vec<usize> = vec![B.len(); n*2-1];
        for i in n-1..n-1+m {
            v[i] = B[i+1-n]
        }
        for i in (0..n-1).rev() {
            v[i] = min(v[i*2+1], v[i*2+2])
        }
        SegmentTree { n, v }
    }
    
    fn rightmost_le_pos(&self, m: usize) -> usize {
        self.rightmost_le_pos_core(m, 0)
    }
    
    fn rightmost_le_pos_core(&self, m: usize, i: usize) -> usize {
        if i >= self.n - 1 {
            i + 1 - self.n
        }
        else {
            if self.v[i*2+2] <= m {
                self.rightmost_le_pos_core(m, i*2+2)
            }
            else {
                self.rightmost_le_pos_core(m, i*2+1)
            }
        }
    }
}


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

fn read_input() -> Vec<usize> {
    let _N: usize = read();
    let A = read_vec();
    A
}

fn find_right_limit(A: &Vec<usize>) -> Vec<usize> {
    let N = A.len();
    let mut L: Vec<usize> = vec![N-1; N];
    let mut j: usize = 0;
    for i in 0..N-1 {
        while j < N && 1 + j <= A[j] + i {
            j += 1
        }
        L[i] = j - 1
    }
    L
}

fn find_left_limit(A: &Vec<usize>) -> Vec<usize> {
    let N = A.len();
    let mut L: Vec<usize> = vec![0; N];
    let mut j: usize = N - 1;
    for i in (1..N).rev() {
        while 1 + i <= A[j] + j {
            if j == 0 {
                break
            }
            j -= 1
        }
        L[i] = j + 1
    }
    L
}

fn F(A: Vec<usize>) -> usize {
    let N = A.len();
    let L = find_right_limit(&A);
    let R = find_left_limit(&A);
    
    let tree = SegmentTree::create(R);
    let mut max_size = 0;
    for i in 0..N {
        let j = tree.rightmost_le_pos(L[i]);
        max_size = max(max_size, (j - i + 2) / 2)
    }
    max_size
}

fn main() {
    let A = read_input();
    println!("{}", F(A))
}