Submission #61624943

---

Source Code Expand

use ac_library::{Max, Segtree};
#[allow(unused_imports)]
use proconio::{input, marker::Usize1};

fn main() {
    input!{
        n: usize,
        mut a: [u64; n],
        q: usize,
    }
    a.push(INF);
    let mut seg :Segtree<Max<usize>> = Segtree::new(n);
    for (i, ai) in a[0..n].iter().enumerate() {
        seg.set(i, a.lower_bound(*ai * 2) - i);
    }

    let check = |l: usize, r: usize, k: usize| -> bool {
        let val = seg.prod(l..l+k);
        l+k-1+val.max(k)<=r
    };

    for _ in 0..q {
        input! {
            l: Usize1,
            r: Usize1
        }

        // 無駄にlogがつくが、シンプルな二分探索をする
        let mut ok = 0;
        let mut ng = n-l;

        while ng-ok>1 {
            let mid = (ok+ng)/2;
            if check(l, r, mid) {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        println!("{}", ok);
    }
}

pub trait Debuggable {
    fn debug_string(&self) -> String;
}

impl<T: std::fmt::Debug + std::fmt::Display> Debuggable for Vec<T> {
    fn debug_string(&self) -> String {
        use itertools::Itertools;
        use std::iter::repeat;
        if let Some(max_size) = self.iter()
            .enumerate()
            .map(|(i, x)| (format!("{:?}", x).len()).max(format!("{:?}", i).len()))
            .max() {
                let mut idx = String::from("idx |");   
                let mut val = String::from("val |");   
                for (i, xi) in self.iter().enumerate() {
                    idx.push_str(
                        &format!(" {:>w$} |", i, w=max_size)
                    );
                    val.push_str(
                        &format!(" {:>w$} |", xi, w=max_size)
                    );
                }

                format!("{}\n{}\n{}\n", idx, repeat('-').take(idx.len()).join(""), val)
            } else {
                format!("idx | \nval |\n")
            }
    }
}

impl<T: std::fmt::Debug + std::fmt::Display> Debuggable for std::collections::BTreeSet<T> {
    fn debug_string(&self) -> String {
        use itertools::Itertools;
        format!("{{ {} }}", self.iter().join(", "))
    }
}

impl<T, U> Debuggable for std::collections::BTreeMap<T, U> 
where T: std::fmt::Debug + std::fmt::Display, U: std::fmt::Debug + std::fmt::Display
{
    fn debug_string(&self) -> String {
        use itertools::Itertools;
        format!(
            "{{\n{}\n }}", self.iter()
                .map(|(k, v)| format!("{k} -> {v}, "))
                .join("\n")
        )
    }
}

// lg! マクロの定義
#[macro_export]
macro_rules! lg {
    ($val:expr) => {
        #[cfg(feature = "local")]
        {
            {
                use Debuggable;
                let val = &$val;
                eprintln!(
                    "[{}:{}] {} = \n{}",
                    file!(),
                    line!(),
                    stringify!($val),
                    val.debug_string()
                );
                val
            }
        }
    }
}
    pub static INF: u64 = 1e18 as u64;
pub static DI: &[usize] = &[0, !0, 0, 1, !0, 1, !0, 1];
pub static DJ: &[usize] = &[!0, 0, 1, 0, !0, !0, 1, 1];
pub static DC: &[char] = &['L', 'U', 'R', 'D'];
pub trait VecLibs<T: std::cmp::Ord> {
    fn lower_bound(&self, elm: T) -> usize;
    fn upper_bound(&self, elm: T) -> usize;
}

impl<T: std::cmp::Ord> VecLibs<T> for Vec<T> {
    fn lower_bound(&self, elm: T) -> usize {
        let mut left = 0;
        let mut right = self.len();
        while left < right {
            let mid = (left + right) / 2;
            if self[mid] < elm {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        left
    }

    fn upper_bound(&self, elm: T) -> usize {
        let mut left = 0;
        let mut right = self.len();
        while left < right {
            let mid = (left + right) / 2;
            if self[mid] <= elm {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        left
    }
}

Submission Info

Judge Result