Submission #61589296

---

Source Code Expand

use ac_library::{Additive, LazySegtree, MapMonoid};
use itertools::Itertools;
use proconio::{input, marker::Chars};
use std::collections::{BTreeMap, HashMap};

pub fn main() {
    input! {
        n: usize,
        an: [usize; n]
    };
    struct Add;
    impl MapMonoid for Add {
        type M = Additive<usize>;
        type F = usize;

        fn identity_map() -> Self::F {
            0
        }
        fn mapping(
            f: &Self::F,
            x: &<Self::M as ac_library::Monoid>::S,
        ) -> <Self::M as ac_library::Monoid>::S {
            f + x
        }
        fn composition(f: &Self::F, g: &Self::F) -> Self::F {
            f + g
        }
    }
    let mut segtree: LazySegtree<Add> = an.clone().into();
    for i in 0..n {
        let m = segtree.get(i);
        segtree.apply_range((i + 1).min(n)..(i + m + 1).min(n), 1);
        segtree.set(i, if m < (n - 1 - i) { 0 } else { m - (n - 1 - i) });
    }
    let mut ans = vec![0; n];
    for i in 0..n {
        ans[i] = segtree.get(i);
    }
    println!("{}", ans.iter().join(" "));
}

Submission Info

Compile Error

warning: unused import: `marker::Chars`
 --> src/main.rs:3:23
  |
3 | use proconio::{input, marker::Chars};
  |                       ^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unused imports: `BTreeMap`, `HashMap`
 --> src/main.rs:4:24
  |
4 | use std::collections::{BTreeMap, HashMap};
  |                        ^^^^^^^^  ^^^^^^^

Judge Result