#957795 (Rust) No.2673 A present from B

• 問題: No.2673 A present from B
• ユーザー: ngtkana
• 提出日時: 2024-03-06 00:47:57
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 16,587 bytes
• コンパイル時間: 12,927 ms
• コンパイル使用メモリ: 401,664 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-09-29 23:33:08
• 合計ジャッジ時間: 13,968 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	1 ms; 5,248 KB
testcase_03	AC	1 ms; 5,248 KB
testcase_04	AC	1 ms; 5,248 KB
testcase_05	AC	1 ms; 5,248 KB
testcase_06	AC	2 ms; 5,248 KB
testcase_07	AC	1 ms; 5,248 KB
testcase_08	AC	1 ms; 5,248 KB
testcase_09	AC	1 ms; 5,248 KB
testcase_10	AC	1 ms; 5,248 KB
testcase_11	AC	1 ms; 5,248 KB
testcase_12	AC	2 ms; 5,248 KB
testcase_13	AC	1 ms; 5,248 KB
testcase_14	AC	1 ms; 5,248 KB
testcase_15	AC	1 ms; 5,248 KB
testcase_16	AC	1 ms; 5,248 KB
testcase_17	AC	1 ms; 5,248 KB
testcase_18	AC	1 ms; 5,248 KB
testcase_19	AC	1 ms; 5,248 KB
testcase_20	AC	1 ms; 5,248 KB
testcase_21	AC	2 ms; 5,248 KB
testcase_22	AC	1 ms; 5,248 KB
testcase_23	AC	1 ms; 5,248 KB
testcase_24	AC	1 ms; 5,248 KB
testcase_25	AC	1 ms; 5,248 KB
testcase_26	AC	1 ms; 5,248 KB

ソースコード

use input::input_array;
use input::input_vec;
use std::cmp::Ordering;
use veb::VebMap;

fn main() {
    let [n, _m] = input_array::<usize, 2>();
    let a = input_vec::<usize>();
    let mut dist = VebMap::new(n + 2);
    dist.insert(0, usize::MAX);
    dist.insert(1, 0);
    dist.insert(n, n - 1);
    dist.insert(n + 1, usize::MAX);
    for &x1 in a.iter().rev() {
        let x2 = x1 + 1;
        lerp(&mut dist, x1);
        lerp(&mut dist, x2);
        match dist[x1].cmp(&dist[x2]) {
            Ordering::Equal => {}
            Ordering::Less => {
                let section = dist[x1] as isize - x1 as isize;
                let on_line = |x: usize, y: usize| y == x.checked_add_signed(section).unwrap();
                lerp(&mut dist, x1 - 1);
                if dist[x1 - 1] >= dist[x1] {
                    *dist.get_mut(x1).unwrap() += 1;
                }
                if let Some((mut x3, &(mut y3))) = dist.succ(x2).filter(|&(x, &y)| on_line(x, y)) {
                    while let Some((x, &y)) = dist.succ(x3).filter(|&(x, &y)| on_line(x, y)) {
                        dist.remove(x3);
                        (x3, y3) = (x, y);
                    }
                    lerp(&mut dist, x3 + 1);
                    dist.insert(x3, y3 - 1);
                }
                let y2 = dist[x2];
                dist.insert(x2, y2 - 1);
            }
            Ordering::Greater => {
                let section = x2 as isize - dist[x2] as isize;
                let on_line = |x: usize, y: usize| y == x.checked_add_signed(section).unwrap();
                lerp(&mut dist, x2 + 1);
                if dist[x2 + 1] >= dist[x2] {
                    *dist.get_mut(x2).unwrap() += 1;
                }
                if let Some((mut x3, &(mut y3))) = dist.pred(x1).filter(|&(x, &y)| on_line(x, y)) {
                    while let Some((x, &y)) = dist.pred(x3).filter(|&(x, &y)| on_line(x, y)) {
                        dist.remove(x3);
                        (x3, y3) = (x, y);
                    }
                    lerp(&mut dist, x3 - 1);
                    dist.insert(x3, y3 - 1);
                }
                let y1 = dist[x1];
                dist.insert(x1, y1 - 1);
            }
        }
    }
    println!(
        "{}",
        (2..=n)
            .map(|i| {
                lerp(&mut dist, i);
                dist.get(i).unwrap().to_string()
            })
            .collect::<Vec<_>>()
            .join(" ")
    );
}

fn lerp(map: &mut VebMap<usize>, x: usize) {
    if !map.contains_key(x) {
        let (x0, &y0) = map.pred(x).unwrap();
        let (x1, &y1) = map.succ(x).unwrap();
        assert!(y0 == y1 || y0.abs_diff(y1) == x1 - x0);
        let y = y0 + (x - x0) * (y1 - y0) / (x1 - x0);
        map.insert(x, y);
    }
}

// input {{{
#[allow(dead_code)]
mod input {
    use std::cell::Cell;
    use std::convert::TryFrom;
    use std::io::stdin;
    use std::io::BufRead;
    use std::io::BufReader;
    use std::io::Lines;
    use std::io::Stdin;
    use std::str::FromStr;
    use std::sync::Mutex;
    use std::sync::Once;
    type Server = Mutex<Lines<BufReader<Stdin>>>;
    static ONCE: Once = Once::new();
    pub struct Lazy(Cell<Option<Server>>);
    unsafe impl Sync for Lazy {}
    fn line() -> String {
        static SYNCER: Lazy = Lazy(Cell::new(None));
        ONCE.call_once(|| {
            SYNCER
                .0
                .set(Some(Mutex::new(BufReader::new(stdin()).lines())));
        });
        unsafe {
            (*SYNCER.0.as_ptr())
                .as_ref()
                .unwrap()
                .lock()
                .unwrap()
                .next()
                .unwrap()
                .unwrap()
        }
    }
    pub trait ForceFromStr: FromStr {
        fn force_from_str(s: &str) -> Self;
    }
    impl<T, E> ForceFromStr for T
    where
        T: FromStr<Err = E>,
        E: std::fmt::Debug,
    {
        fn force_from_str(s: &str) -> Self {
            s.parse().unwrap()
        }
    }
    pub fn input_array<T: ForceFromStr, const N: usize>() -> [T; N]
    where
        T: std::fmt::Debug,
    {
        <[_; N]>::try_from(input_vec()).unwrap()
    }
    pub fn input_vec<T: ForceFromStr>() -> Vec<T> {
        line()
            .split_whitespace()
            .map(T::force_from_str)
            .collect::<Vec<_>>()
    }
    pub fn input<T: ForceFromStr>() -> T {
        T::force_from_str(&line())
    }
}
// }}}
// veb {{{
#[allow(dead_code)]
mod veb {
    use std::collections::HashMap;
    macro_rules! multi_or_else {
        ($e:expr, $($f:expr),+) => {
            $e.or_else(|| multi_or_else!($($f),+))
        };
        ($e:expr) => {
            $e
        };
    }
    pub struct VebMap<V> {
        veb: VebSet,
        map: HashMap<usize, V>,
    }
    impl<V> VebMap<V> {
        pub fn new(n: usize) -> Self {
            Self {
                veb: VebSet::new(n),
                map: HashMap::new(),
            }
        }

        pub fn insert(&mut self, i: usize, v: V) -> Option<V> {
            self.veb.insert(i);
            self.map.insert(i, v)
        }

        pub fn remove(&mut self, i: usize) -> Option<V> {
            self.veb.remove(i);
            self.map.remove(&i)
        }

        pub fn get(&self, i: usize) -> Option<&V> {
            self.map.get(&i)
        }

        pub fn get_mut(&mut self, i: usize) -> Option<&mut V> {
            self.map.get_mut(&i)
        }

        pub fn min_key(&self) -> Option<usize> {
            self.veb.min()
        }

        pub fn min_value(&self) -> Option<&V> {
            self.veb.min().and_then(|i| self.map.get(&i))
        }

        pub fn min(&self) -> Option<(usize, &V)> {
            self.veb
                .min()
                .and_then(|i| self.map.get(&i).map(|v| (i, v)))
        }

        pub fn max_key(&self) -> Option<usize> {
            self.veb.max()
        }

        pub fn max_value(&self) -> Option<&V> {
            self.veb.max().and_then(|i| self.map.get(&i))
        }

        pub fn max(&self) -> Option<(usize, &V)> {
            self.veb
                .max()
                .and_then(|i| self.map.get(&i).map(|v| (i, v)))
        }

        pub fn succ_key(&self, i: usize) -> Option<usize> {
            self.veb.succ(i)
        }

        pub fn succ_value(&self, i: usize) -> Option<&V> {
            self.veb.succ(i).and_then(|i| self.map.get(&i))
        }

        pub fn succ(&self, i: usize) -> Option<(usize, &V)> {
            self.veb
                .succ(i)
                .and_then(|i| self.map.get(&i).map(|v| (i, v)))
        }

        pub fn pred_key(&self, i: usize) -> Option<usize> {
            self.veb.pred(i)
        }

        pub fn pred_value(&self, i: usize) -> Option<&V> {
            self.veb.pred(i).and_then(|i| self.map.get(&i))
        }

        pub fn pred(&self, i: usize) -> Option<(usize, &V)> {
            self.veb
                .pred(i)
                .and_then(|i| self.map.get(&i).map(|v| (i, v)))
        }

        pub fn len(&self) -> usize {
            self.veb.len()
        }

        pub fn is_empty(&self) -> bool {
            self.veb.is_empty()
        }

        pub fn contains_key(&self, i: usize) -> bool {
            self.veb.contains(i)
        }

        pub fn collect(&self) -> Vec<(usize, &V)> {
            self.veb
                .collect()
                .into_iter()
                .filter_map(|i| self.map.get(&i).map(|v| (i, v)))
                .collect()
        }
    }
    impl<V> std::ops::Index<usize> for VebMap<V> {
        type Output = V;

        fn index(&self, i: usize) -> &V {
            self.get(i).unwrap()
        }
    }
    impl<V> std::ops::IndexMut<usize> for VebMap<V> {
        fn index_mut(&mut self, i: usize) -> &mut V {
            self.get_mut(i).unwrap()
        }
    }
    pub enum VebSet {
        Internal {
            min: usize,
            max: usize,
            len: usize,
            csize: usize,
            summary: Box<VebSet>,
            chunks: HashMap<usize, VebSet>,
        },
        Leaf(u64),
    }
    impl VebSet {
        pub fn new(n: usize) -> Self {
            if n <= 64 {
                VebSet::Leaf(0)
            } else {
                let csize = (n as f64).sqrt().ceil() as usize;
                let ccount = (n + csize - 1) / csize;
                Self::Internal {
                    min: 0,
                    max: 0,
                    csize,
                    len: 0,
                    summary: Box::new(VebSet::new(ccount)),
                    chunks: HashMap::new(),
                }
            }
        }

        pub fn min(&self) -> Option<usize> {
            match self {
                Self::Internal { min, len, .. } => Some(*min).filter(|_| *len > 0),
                Self::Leaf(bs) => Some(bs.trailing_zeros() as usize).filter(|&i| i < 64),
            }
        }

        pub fn max(&self) -> Option<usize> {
            match self {
                Self::Internal { max, len, .. } => Some(*max).filter(|_| *len > 0),
                Self::Leaf(bs) => bs.checked_ilog2().map(|i| i as usize),
            }
        }

        pub fn len(&self) -> usize {
            match self {
                Self::Internal { len, .. } => *len,
                Self::Leaf(bs) => bs.count_ones() as usize,
            }
        }

        pub fn is_empty(&self) -> bool {
            self.len() == 0
        }

        pub fn insert(&mut self, mut i: usize) -> bool {
            match self {
                Self::Internal {
                    min,
                    max,
                    csize,
                    len,
                    summary,
                    chunks,
                } => {
                    if *len == 0 {
                        *min = i;
                        *max = i;
                        *len = 1;
                        true
                    } else {
                        if i < *min {
                            std::mem::swap(&mut i, min);
                        }
                        *max = (*max).max(i);
                        if i == *min {
                            return false;
                        }
                        let j = i / *csize;
                        let k = i % *csize;
                        let result = if let Some(chunk) = chunks.get_mut(&j) {
                            chunk.insert(k)
                        } else {
                            let mut chunk = VebSet::new(*csize);
                            assert!(chunk.insert(k));
                            chunks.insert(j, chunk);
                            summary.insert(j);
                            true
                        };
                        if result {
                            *len += 1;
                        }
                        result
                    }
                }
                Self::Leaf(bs) => {
                    let result = *bs >> i & 1;
                    *bs |= 1 << i;
                    result == 0
                }
            }
        }

        pub fn remove(&mut self, mut i: usize) -> bool {
            match self {
                Self::Internal {
                    min,
                    max,
                    csize,
                    len,
                    summary,
                    chunks,
                } => match len {
                    0 => false,
                    1 => {
                        let result = i == *min;
                        if result {
                            *min = 0;
                            *max = 0;
                            *len = 0;
                        }
                        result
                    }
                    _ => {
                        if i == *min {
                            let j = summary.min().unwrap();
                            i = j * *csize + chunks[&j].min().unwrap();
                            *min = i;
                        }
                        let j = i / *csize;
                        let k = i % *csize;
                        let result = chunks.get_mut(&j).map_or(false, |chunk| chunk.remove(k));
                        if result {
                            *len -= 1;
                            if chunks[&j].is_empty() {
                                chunks.remove(&j);
                                summary.remove(j);
                            }
                            if i == *max {
                                *max = if let Some(j) = summary.max() {
                                    j * *csize + chunks[&j].max().unwrap()
                                } else {
                                    *min
                                };
                            }
                        }
                        result
                    }
                },
                Self::Leaf(bs) => {
                    let result = *bs >> i & 1;
                    *bs &= !(1 << i);
                    result == 1
                }
            }
        }

        pub fn succ(&self, i: usize) -> Option<usize> {
            match self {
                Self::Internal {
                    min,
                    max,
                    len,
                    csize,
                    summary,
                    chunks,
                    ..
                } => {
                    let j = i / csize;
                    let k = i % csize;
                    match () {
                        () if *len == 0 || *max <= i => None,
                        () if i < *min => Some(*min),
                        () => multi_or_else!(
                            chunks
                                .get(&j)
                                .and_then(|chunk| chunk.succ(k))
                                .map(|k1| j * csize + k1),
                            summary
                                .succ(j)
                                .map(|j1| j1 * csize + chunks[&j1].min().unwrap())
                        ),
                    }
                }
                &Self::Leaf(bs) => match i {
                    63 => None,
                    _ => Some(i + 1 + (bs >> (i + 1)).trailing_zeros() as usize)
                        .filter(|&i1| i1 < 64),
                },
            }
        }

        pub fn pred(&self, i: usize) -> Option<usize> {
            match self {
                Self::Internal {
                    min,
                    max,
                    csize,
                    len,
                    summary,
                    chunks,
                } => {
                    let j = i / csize;
                    let k = i % csize;
                    match () {
                        () if *len == 0 || i <= *min => None,
                        () if *max < i => Some(*max),
                        () => multi_or_else!(
                            chunks
                                .get(&j)
                                .and_then(|chunk| chunk.pred(k))
                                .map(|k1| { j * csize + k1 }),
                            summary
                                .pred(j)
                                .map(|j1| { j1 * csize + chunks[&j1].max().unwrap() }),
                            Some(*min)
                        ),
                    }
                }
                &Self::Leaf(bs) => (bs & ((1 << i) - 1)).checked_ilog2().map(|j| j as usize),
            }
        }

        pub fn contains(&self, i: usize) -> bool {
            match self {
                Self::Internal {
                    min,
                    csize,
                    len,
                    chunks,
                    ..
                } => {
                    let j = i / csize;
                    let k = i % csize;
                    *len != 0
                        && (i == *min || chunks.get(&j).map_or(false, |chunk| chunk.contains(k)))
                }
                Self::Leaf(bs) => bs >> i & 1 == 1,
            }
        }

        pub fn collect(&self) -> Vec<usize> {
            let mut result = Vec::with_capacity(self.len());
            let mut i = self.min();
            for _ in 0..self.len() {
                result.push(i.unwrap());
                i = self.succ(i.unwrap());
            }
            result
        }
    }
    impl std::fmt::Debug for VebSet {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            f.debug_set().entries(self.collect()).finish()
        }
    }
}
// }}}