Submission #37192377

---

Source Code Expand

use proconio::input;

use nekolib::{
    ds::VecSegtree,
    traits::{Fold, GetMut, Identity},
    utils::{OpAdd, OpMax, OpMin, SpaceSep},
};

fn main() {
    input! {
        n: usize,
        m: usize,
        k: usize,
        a: [i64; n],
    }

    if m == k {
        let a: VecSegtree<OpAdd<_>> = a.into();
        let res: Vec<_> = (m..=n).map(|r| a.fold(r - m..r)).collect();
        println!("{}", SpaceSep(&res));
        return;
    }

    let oo = OpMin::<i64>::default().id();
    let oo_neg = OpMax::<i64>::default().id();

    let mut sum0: VecSegtree<OpAdd<usize>> = vec![0; n].into();
    let mut sum1: VecSegtree<OpAdd<i64>> = vec![0; n].into();
    let mut used = VecSegtree::<OpMax<(i64, usize)>>::new(n);
    let mut unused = VecSegtree::<OpMin<(i64, usize)>>::new(n);

    for i in 0..n {
        used.get_mut(i).unwrap().1 = i;
        unused.get_mut(i).unwrap().1 = i;
    }

    let mut res = vec![];
    for i in 0..n {
        // push(i)
        *sum0.get_mut(i).unwrap() = 1;
        *sum1.get_mut(i).unwrap() = a[i];
        used.get_mut(i).unwrap().0 = a[i];

        if sum0.fold(..) > k {
            // unuse_max()
            let pop = used.fold(..).1;
            *sum0.get_mut(pop).unwrap() = 0;
            *sum1.get_mut(pop).unwrap() = 0;
            used.get_mut(pop).unwrap().0 = oo_neg;
            unused.get_mut(pop).unwrap().0 = a[pop];
        }

        if i >= m - 1 {
            res.push(sum1.fold(..));

            let j = i - (m - 1);
            if sum0[j] > 0 {
                // pop(j)
                *sum0.get_mut(j).unwrap() = 0;
                *sum1.get_mut(j).unwrap() = 0;
                used.get_mut(j).unwrap().0 = oo_neg;

                // use_min()
                let push = unused.fold(..).1;
                *sum0.get_mut(push).unwrap() = 1;
                *sum1.get_mut(push).unwrap() = a[push];
                used.get_mut(push).unwrap().0 = a[push];
                unused.get_mut(push).unwrap().0 = oo;
            } else {
                // pop(j)
                unused.get_mut(j).unwrap().0 = oo;
            }
        }
    }

    println!("{}", SpaceSep(&res));
}

/// This module is bundled automatically.
/// See <https://rsk0315.github.io/library-rs/nekolib/> for documentation.
pub mod nekolib {
    pub mod ds {
        pub mod vec_segtree {
            use super::super::traits::binop;
            use super::super::traits::fold;
            use super::super::traits::fold_bisect;
            use super::super::traits::get_mut;
            use super::super::traits::set_value;
            use super::super::utils::buf_range;
            use binop::Monoid;
            use buf_range::{bounds_within, check_bounds, check_bounds_range};
            use fold::Fold;
            use fold_bisect::{FoldBisect, FoldBisectRev};
            use get_mut::GetMut;
            use set_value::SetValue;
            use std::convert::From;
            use std::fmt::{self, Debug};
            use std::iter::{IntoIterator, Iterator};
            use std::ops::{Deref, DerefMut, Index, Range, RangeBounds};
            #[derive(Clone)]
            pub struct VecSegtree<M>
            where
                M: Monoid,
                M::Set: Clone,
            {
                buf: Vec<M::Set>,
                len: usize,
                monoid: M,
            }
            impl<M> VecSegtree<M>
            where
                M: Monoid,
                M::Set: Clone,
            {
                #[must_use]
                pub fn new(len: usize) -> Self
                where
                    M: Default,
                {
                    let monoid = M::default();
                    Self { len, buf: vec![monoid.id(); len + len], monoid }
                }
                pub fn is_empty(&self) -> bool { self.len == 0 }
                pub fn len(&self) -> usize { self.len }
                fn nodes(&self, l: usize, r: usize) -> Vec<usize> {
                    let mut l = self.len + l;
                    let mut r = self.len + r;
                    let mut vl = vec![];
                    let mut vr = vec![];
                    while l < r {
                        if l & 1 == 1 {
                            vl.push(l);
                            l += 1;
                        }
                        if r & 1 == 1 {
                            r -= 1;
                            vr.push(r);
                        }
                        l >>= 1;
                        r >>= 1;
                    }
                    vr.reverse();
                    vl.append(&mut vr);
                    vl
                }
                fn nodes_rev(&self, l: usize, r: usize) -> Vec<usize> {
                    self.nodes(l, r).into_iter().rev().collect()
                }
            }
            impl<M, B> Fold<B> for VecSegtree<M>
            where
                M: Monoid,
                M::Set: Clone,
                B: RangeBounds<usize>,
            {
                type Output = M;
                fn fold(&self, b: B) -> M::Set {
                    let Range { start, end } = bounds_within(b, self.len);
                    let mut il = self.len + start;
                    let mut ir = self.len + end;
                    let mut res_l = self.monoid.id();
                    let mut res_r = self.monoid.id();
                    while il < ir {
                        if il & 1 == 1 {
                            res_l = self.monoid.op(res_l, self.buf[il].clone());
                            il += 1;
                        }
                        if ir & 1 == 1 {
                            ir -= 1;
                            res_r = self.monoid.op(self.buf[ir].clone(), res_r);
                        }
                        il >>= 1;
                        ir >>= 1;
                    }
                    self.monoid.op(res_l, res_r)
                }
            }
            impl<M> SetValue<usize> for VecSegtree<M>
            where
                M: Monoid,
                M::Set: Clone,
            {
                type Input = M::Set;
                fn set_value(&mut self, i: usize, x: Self::Input) {
                    check_bounds(i, self.len);
                    *self.get_mut(i).unwrap() = x;
                }
            }
            pub struct GetMutIndex<'a, M>
            where
                M: Monoid,
                M::Set: Clone,
            {
                tree: &'a mut VecSegtree<M>,
                index: usize,
            }
            impl<'a, M: 'a> GetMut<'a> for VecSegtree<M>
            where
                M: Monoid,
                M::Set: Clone,
            {
                type Output = GetMutIndex<'a, M>;
                fn get_mut(
                    &'a mut self,
                    index: usize,
                ) -> Option<GetMutIndex<'a, M>> {
                    if index < self.len {
                        Some(GetMutIndex { tree: self, index })
                    } else {
                        None
                    }
                }
            }
            impl<M> Drop for GetMutIndex<'_, M>
            where
                M: Monoid,
                M::Set: Clone,
            {
                fn drop(&mut self) {
                    let mut i = self.tree.len + self.index;
                    while i > 1 {
                        i >>= 1;
                        self.tree.buf[i] = self.tree.monoid.op(
                            self.tree.buf[i << 1].clone(),
                            self.tree.buf[i << 1 | 1].clone(),
                        );
                    }
                }
            }
            impl<M> Deref for GetMutIndex<'_, M>
            where
                M: Monoid,
                M::Set: Clone,
            {
                type Target = M::Set;
                fn deref(&self) -> &Self::Target {
                    &self.tree.buf[self.tree.len + self.index]
                }
            }
            impl<M> DerefMut for GetMutIndex<'_, M>
            where
                M: Monoid,
                M::Set: Clone,
            {
                fn deref_mut(&mut self) -> &mut Self::Target {
                    &mut self.tree.buf[self.tree.len + self.index]
                }
            }
            impl<M> Default for VecSegtree<M>
            where
                M: Monoid + Default,
                M::Set: Clone,
            {
                fn default() -> Self {
                    Self { buf: vec![], len: 0, monoid: M::default() }
                }
            }
            impl<M> From<Vec<M::Set>> for VecSegtree<M>
            where
                M: Monoid + Default,
                M::Set: Clone,
            {
                fn from(v: Vec<M::Set>) -> Self {
                    Self::from((v, M::default()))
                }
            }
            impl<M> From<(Vec<M::Set>, M)> for VecSegtree<M>
            where
                M: Monoid,
                M::Set: Clone,
            {
                fn from((mut v, monoid): (Vec<M::Set>, M)) -> Self {
                    let len = v.len();
                    let mut buf = vec![monoid.id(); len];
                    buf.append(&mut v);
                    for i in (0..len).rev() {
                        buf[i] = monoid
                            .op(buf[i << 1].clone(), buf[i << 1 | 1].clone());
                    }
                    Self { buf, len, monoid }
                }
            }
            impl<M> Index<usize> for VecSegtree<M>
            where
                M: Monoid,
                M::Set: Clone,
            {
                type Output = M::Set;
                fn index(&self, i: usize) -> &Self::Output {
                    check_bounds(i, self.len);
                    &self.buf[i + self.len]
                }
            }
            impl<M> From<VecSegtree<M>> for Vec<M::Set>
            where
                M: Monoid,
                M::Set: Clone,
            {
                fn from(v: VecSegtree<M>) -> Self {
                    v.buf.into_iter().skip(v.len).collect()
                }
            }
            impl<M> Debug for VecSegtree<M>
            where
                M: Monoid,
                M::Set: Clone + Debug,
            {
                fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
                    f.debug_list().entries(self.buf[self.len..].iter()).finish()
                }
            }
            impl<M> FoldBisect for VecSegtree<M>
            where
                M: Monoid,
                M::Set: Clone,
            {
                fn fold_bisect<F>(&self, l: usize, pred: F) -> (usize, M::Set)
                where
                    F: Fn(&M::Set) -> bool,
                {
                    check_bounds_range(l, 0..=self.len);
                    let mut x = self.monoid.id();
                    assert!(pred(&x), "`pred(id)` must hold");
                    match self.fold(l..) {
                        x if pred(&x) => return (self.len, x),
                        _ => {}
                    }
                    for v in self.nodes(l, self.len) {
                        let tmp =
                            self.monoid.op(x.clone(), self.buf[v].clone());
                        if pred(&tmp) {
                            x = tmp;
                            continue;
                        }
                        let mut v = v;
                        while v < self.len {
                            v <<= 1;
                            let tmp =
                                self.monoid.op(x.clone(), self.buf[v].clone());
                            if pred(&tmp) {
                                x = tmp;
                                v += 1;
                            }
                        }
                        return (v - self.len, x);
                    }
                    unreachable!();
                }
            }
            impl<M> FoldBisectRev for VecSegtree<M>
            where
                M: Monoid,
                M::Set: Clone,
            {
                fn fold_bisect_rev<F>(
                    &self,
                    r: usize,
                    pred: F,
                ) -> (usize, M::Set)
                where
                    F: Fn(&M::Set) -> bool,
                {
                    check_bounds_range(r, 0..=self.len);
                    let mut x = self.monoid.id();
                    assert!(pred(&x), "`pred(id)` must hold");
                    match self.fold(..r) {
                        x if pred(&x) => return (0, x),
                        _ => {}
                    }
                    for v in self.nodes_rev(0, r) {
                        let tmp =
                            self.monoid.op(self.buf[v].clone(), x.clone());
                        if pred(&tmp) {
                            x = tmp;
                            continue;
                        }
                        let mut v = v;
                        while v < self.len {
                            v = v << 1 | 1;
                            let tmp =
                                self.monoid.op(self.buf[v].clone(), x.clone());
                            if pred(&tmp) {
                                x = tmp;
                                v -= 1;
                            }
                        }
                        return (v - self.len + 1, x);
                    }
                    unreachable!();
                }
            }
        }
        pub use self::vec_segtree::VecSegtree;
    }
    pub mod traits {
        pub mod additive {
            use std::ops::Add;
            pub trait Zero: Add<Output = Self> + Sized {
                fn zero() -> Self;
            }
            pub trait AddAssoc: Add<Output = Self> + Sized {}
            pub trait AddComm: Add<Output = Self> + Sized {}
            macro_rules ! impl_trait { ($ (impl ($ T : ty) for { $ ($ U : ty) ,* } $ S : tt) *) => { $ ($ (impl $ T for $ U $ S) *) * } ; }
            impl_trait! { impl (Zero) for { i8 , i16 , i32 , i64 , i128 , isize , u8 , u16 , u32 , u64 , u128 , usize } { fn zero () -> Self { 0 } } impl (AddAssoc) for { i8 , i16 , i32 , i64 , i128 , isize , u8 , u16 , u32 , u64 , u128 , usize } { } impl (AddComm) for { i8 , i16 , i32 , i64 , i128 , isize , u8 , u16 , u32 , u64 , u128 , usize } { } }
        }
        pub use self::additive::{AddAssoc, AddComm, Zero};
        pub mod binop {
            pub trait Magma {
                type Set: Eq;
                fn op(&self, x: Self::Set, y: Self::Set) -> Self::Set;
            }
            pub trait Associative: Magma {}
            pub trait Identity: Magma {
                fn id(&self) -> Self::Set;
            }
            pub trait Commutative: Magma {}
            pub trait PartialRecip: Magma {
                fn partial_recip(&self, x: Self::Set) -> Option<Self::Set>;
            }
            pub trait Recip: PartialRecip {
                fn recip(&self, x: Self::Set) -> Self::Set {
                    self.partial_recip(x).unwrap()
                }
            }
            pub trait Distributive<A: Magma> {}
            pub trait Semigroup: Associative + Magma {}
            impl<G: Associative + Magma> Semigroup for G {}
            pub trait Monoid: Identity + Semigroup {}
            impl<G: Identity + Semigroup> Monoid for G {}
            pub trait CommutativeMonoid: Commutative + Monoid {}
            impl<G: Commutative + Monoid> CommutativeMonoid for G {}
            pub trait Group: Monoid + Recip {}
            impl<G: Monoid + Recip> Group for G {}
            pub trait CommutativeGroup: Commutative + Monoid + Recip {}
            impl<G: Commutative + Monoid + Recip> CommutativeGroup for G {}
            pub trait Ring {
                type Set: Eq;
                type Additive: CommutativeGroup<Set = Self::Set>;
                type Multiplicative: Monoid<Set = Self::Set>
                    + Distributive<Self::Additive>;
                fn additive(&self) -> &Self::Additive;
                fn multiplicative(&self) -> &Self::Multiplicative;
                fn add(&self, x: Self::Set, y: Self::Set) -> Self::Set {
                    self.additive().op(x, y)
                }
                #[must_use]
                fn zero(&self) -> Self::Set { self.additive().id() }
                fn neg(&self, x: Self::Set) -> Self::Set {
                    self.additive().recip(x)
                }
                fn mul(&self, x: Self::Set, y: Self::Set) -> Self::Set {
                    self.multiplicative().op(x, y)
                }
                #[must_use]
                fn one(&self) -> Self::Set { self.multiplicative().id() }
            }
            pub trait CommutativeRing: Ring
            where
                Self::Multiplicative: Commutative,
            {
            }
            pub trait Field: Ring
            where
                Self::Multiplicative: PartialRecip,
            {
                fn recip(&self, x: Self::Set) -> Self::Set {
                    if x == self.additive().id() {
                        panic!(
                            "zero element does not have multiplicative inverse"
                        );
                    } else {
                        self.multiplicative().partial_recip(x).unwrap()
                    }
                }
            }
        }
        pub use self::binop::{
            Associative, Commutative, CommutativeGroup, CommutativeMonoid,
            CommutativeRing, Distributive, Field, Group, Identity, Magma,
            Monoid, PartialRecip, Recip, Ring, Semigroup,
        };
        pub mod fold {
            use super::binop;
            use binop::{Magma, Monoid};
            use std::ops::RangeBounds;
            pub trait Fold<R: RangeBounds<usize>> {
                type Output: Monoid;
                fn fold(&self, r: R) -> <Self::Output as Magma>::Set;
            }
        }
        pub use self::fold::Fold;
        pub mod fold_bisect {
            use super::binop;
            use super::fold;
            use binop::Magma;
            use fold::Fold;
            use std::ops::Range;
            pub trait FoldBisect: Fold<Range<usize>> {
                fn fold_bisect<F>(
                    &self,
                    l: usize,
                    pred: F,
                ) -> (usize, <Self::Output as Magma>::Set)
                where
                    F: Fn(&<Self::Output as Magma>::Set) -> bool;
            }
            pub trait FoldBisectRev: Fold<Range<usize>> {
                fn fold_bisect_rev<F>(
                    &self,
                    r: usize,
                    pred: F,
                ) -> (usize, <Self::Output as Magma>::Set)
                where
                    F: Fn(&<Self::Output as Magma>::Set) -> bool;
            }
        }
        pub use self::fold_bisect::{FoldBisect, FoldBisectRev};
        pub mod get_mut {
            use std::ops::{Deref, DerefMut};
            pub trait GetMut<'a> {
                type Output: Deref + DerefMut;
                fn get_mut(&'a mut self, i: usize) -> Option<Self::Output>;
            }
        }
        pub use self::get_mut::GetMut;
        pub mod max {
            pub trait Max: Ord {
                fn max() -> Self;
            }
            macro_rules ! impl_max { ($ ($ t : ident) ,*) => { $ (impl Max for $ t { fn max () -> Self { std ::$ t :: MAX } }) * } }
            impl_max! { i8 , i16 , i32 , i64 , i128 , isize , u8 , u16 , u32 , u64 , u128 , usize , char }
            impl Max for bool {
                fn max() -> Self { true }
            }
            impl Max for () {
                fn max() -> Self { () }
            }
            impl<A: Max> Max for (A,) {
                fn max() -> Self { (Max::max(),) }
            }
            macro_rules ! impl_tuple { (($ ($ t : ident) ,+)) => { impl < $ ($ t : Max) ,+ > Max for ($ ($ t) ,+) { fn max () -> Self { ($ (<$ t as Max >:: max ()) ,+) } } } ; ($ (($ ($ t : ident) ,+) ,) +) => { $ (impl_tuple ! { ($ ($ t) ,+) }) + } }
            impl_tuple! { (A , B) , (A , B , C) , (A , B , C , D) , (A , B , C , D , E) , (A , B , C , D , E , F) , (A , B , C , D , E , F , G) , (A , B , C , D , E , F , G , H) , (A , B , C , D , E , F , G , H , I) , (A , B , C , D , E , F , G , H , I , J) , (A , B , C , D , E , F , G , H , I , J , K) , (A , B , C , D , E , F , G , H , I , J , K , L) , }
        }
        pub use self::max::Max;
        pub mod min {
            pub trait Min: Ord {
                fn min() -> Self;
            }
            macro_rules ! impl_min { ($ ($ t : ident) ,*) => { $ (impl Min for $ t { fn min () -> Self { std ::$ t :: MIN } }) * } }
            impl_min! { i8 , i16 , i32 , i64 , i128 , isize , u8 , u16 , u32 , u64 , u128 , usize }
            impl Min for bool {
                fn min() -> Self { false }
            }
            impl Min for char {
                fn min() -> Self { '\0' }
            }
            impl Min for () {
                fn min() -> Self { () }
            }
            impl<A: Min> Min for (A,) {
                fn min() -> Self { (Min::min(),) }
            }
            macro_rules ! impl_tuple { (($ ($ t : ident) ,+)) => { impl < $ ($ t : Min) ,+ > Min for ($ ($ t) ,+) { fn min () -> Self { ($ (<$ t as Min >:: min ()) ,+) } } } ; ($ (($ ($ t : ident) ,+) ,) +) => { $ (impl_tuple ! { ($ ($ t) ,+) }) + } }
            impl_tuple! { (A , B) , (A , B , C) , (A , B , C , D) , (A , B , C , D , E) , (A , B , C , D , E , F) , (A , B , C , D , E , F , G) , (A , B , C , D , E , F , G , H) , (A , B , C , D , E , F , G , H , I) , (A , B , C , D , E , F , G , H , I , J) , (A , B , C , D , E , F , G , H , I , J , K) , (A , B , C , D , E , F , G , H , I , J , K , L) , }
        }
        pub use self::min::Min;
        pub mod set_value {
            pub trait SetValue<I> {
                type Input;
                fn set_value(&mut self, i: I, x: Self::Input);
            }
        }
        pub use self::set_value::SetValue;
    }
    pub mod utils {
        pub mod buf_range {
            use std::fmt::Debug;
            use std::ops::Bound::{Excluded, Included, Unbounded};
            use std::ops::{Range, RangeBounds};
            pub fn bounds_within<R: RangeBounds<usize>>(
                r: R,
                len: usize,
            ) -> Range<usize> {
                let e_ex = match r.end_bound() {
                    Included(&e) => e + 1,
                    Excluded(&e) => e,
                    Unbounded => len,
                };
                let s_in = match r.start_bound() {
                    Included(&s) => s,
                    Excluded(&s) => s + 1,
                    Unbounded => 0,
                }
                .min(e_ex);
                s_in..e_ex
            }
            pub fn check_bounds(i: usize, len: usize) {
                assert!(
                    i < len,
                    "index out of bounds: the len is {} but the index is {}",
                    len,
                    i
                );
            }
            pub fn check_bounds_range(
                i: usize,
                range: impl RangeBounds<usize> + Debug,
            ) {
                assert!(
                    range.contains(&i),
                    "index out of bounds: the range is {:?} but the index is {}",
                    range,
                    i
                );
            }
        }
        pub use self::buf_range::{
            bounds_within, check_bounds, check_bounds_range,
        };
        pub mod op_add {
            use super::super::traits::additive;
            use super::super::traits::binop;
            use additive::{AddAssoc, AddComm, Zero};
            use binop::{
                Associative, Commutative, Identity, Magma, PartialRecip, Recip,
            };
            use std::fmt::Debug;
            #[derive(Clone, Copy, Debug, Eq, PartialEq)]
            pub enum OpAdd<T> {
                OpAddV,
                _Marker(T),
            }
            pub use OpAdd::OpAddV;
            impl<T> Default for OpAdd<T> {
                fn default() -> Self { OpAddV }
            }
            use std::ops::{Add, Neg};
            impl<T> Magma for OpAdd<T>
            where
                T: Add<Output = T> + Eq + Sized,
            {
                type Set = T;
                fn op(&self, x: Self::Set, y: Self::Set) -> Self::Set { x + y }
            }
            impl<T> Identity for OpAdd<T>
            where
                T: Add<Output = T> + Eq + Sized + Zero,
            {
                fn id(&self) -> Self::Set { T::zero() }
            }
            impl<T> PartialRecip for OpAdd<T>
            where
                T: Add<Output = T> + Eq + Sized + Neg<Output = T>,
            {
                fn partial_recip(&self, x: Self::Set) -> Option<Self::Set> {
                    Some(-x)
                }
            }
            impl<T> Recip for OpAdd<T>
            where
                T: Add<Output = T> + Eq + Sized + Neg<Output = T>,
            {
                fn recip(&self, x: Self::Set) -> Self::Set { -x }
            }
            impl<T> Associative for OpAdd<T> where T: Add<Output = T> + Eq + Sized + AddAssoc
            {}
            impl<T> Commutative for OpAdd<T> where T: Add<Output = T> + Eq + Sized + AddComm {}
        }
        pub use self::op_add::OpAdd;
        pub mod op_max {
            use super::super::traits::binop;
            use super::super::traits::min;
            use binop::{Associative, Commutative, Identity, Magma};
            use min::Min;
            use std::fmt::Debug;
            #[derive(Clone, Copy, Debug, Eq, PartialEq)]
            pub enum OpMax<T> {
                OpMaxV,
                _Marker(T),
            }
            pub use OpMax::OpMaxV;
            impl<T> Default for OpMax<T> {
                fn default() -> Self { OpMaxV }
            }
            impl<T> Magma for OpMax<T>
            where
                T: Ord + Eq + Sized,
            {
                type Set = T;
                fn op(&self, x: Self::Set, y: Self::Set) -> Self::Set {
                    x.max(y)
                }
            }
            impl<T> Identity for OpMax<T>
            where
                T: Ord + Eq + Sized + Min,
            {
                fn id(&self) -> Self::Set { <T as Min>::min() }
            }
            impl<T> Associative for OpMax<T> where T: Ord + Eq + Sized {}
            impl<T> Commutative for OpMax<T> where T: Ord + Eq + Sized {}
        }
        pub use self::op_max::OpMax;
        pub mod op_min {
            use super::super::traits::binop;
            use super::super::traits::max;
            use binop::{Associative, Commutative, Identity, Magma};
            use max::Max;
            use std::fmt::Debug;
            #[derive(Clone, Copy, Debug, Eq, PartialEq)]
            pub enum OpMin<T> {
                OpMinV,
                _Marker(T),
            }
            pub use OpMin::OpMinV;
            impl<T> Default for OpMin<T> {
                fn default() -> Self { OpMinV }
            }
            impl<T> Magma for OpMin<T>
            where
                T: Ord + Eq + Sized,
            {
                type Set = T;
                fn op(&self, x: Self::Set, y: Self::Set) -> Self::Set {
                    x.min(y)
                }
            }
            impl<T> Identity for OpMin<T>
            where
                T: Ord + Eq + Sized + Max,
            {
                fn id(&self) -> Self::Set { <T as Max>::max() }
            }
            impl<T> Associative for OpMin<T> where T: Ord + Eq + Sized {}
            impl<T> Commutative for OpMin<T> where T: Ord + Eq + Sized {}
        }
        pub use self::op_min::OpMin;
        pub mod output {
            pub struct SpaceSep<'a, D: ?Sized>(pub &'a D);
            pub struct PerLine<'a, D: ?Sized>(pub &'a D);
            pub struct StrSep<'a, D: ?Sized>(pub &'a D, pub &'a str);
            use std::fmt;
            macro_rules ! impl_fmt { ($ (($ fmt : ident , $ fn : ident) ,) *) => { $ (fn $ fn < I > (it : I , sep : & str , f : & mut fmt :: Formatter) -> fmt :: Result where I : IntoIterator , < I as IntoIterator >:: Item : fmt ::$ fmt , { for (i , x) in it . into_iter () . enumerate () { if i > 0 { write ! (f , "{}" , sep) ?; } fmt ::$ fmt :: fmt (& x , f) ?; } Ok (()) } impl <'a , D : 'a > fmt ::$ fmt for SpaceSep <'a , D > where D : ? Sized , &'a D : IntoIterator , <&'a D as IntoIterator >:: Item : fmt ::$ fmt , { fn fmt (& self , f : & mut fmt :: Formatter) -> fmt :: Result { $ fn (self . 0 , " " , f) } } impl <'a , D : 'a > fmt ::$ fmt for PerLine <'a , D > where D : ? Sized , &'a D : IntoIterator , <&'a D as IntoIterator >:: Item : fmt ::$ fmt , { fn fmt (& self , f : & mut fmt :: Formatter) -> fmt :: Result { $ fn (self . 0 , "\n" , f) } } impl <'a , D : 'a > fmt ::$ fmt for StrSep <'a , D > where D : ? Sized , &'a D : IntoIterator , <&'a D as IntoIterator >:: Item : fmt ::$ fmt , { fn fmt (& self , f : & mut fmt :: Formatter) -> fmt :: Result { $ fn (self . 0 , self . 1 , f) } }) * } ; }
            impl_fmt! { (Display , join_display) , (Debug , join_debug) , (Octal , join_octal) , (LowerHex , join_lower_hex) , (UpperHex , join_upper_hex) , (Pointer , join_pointer) , (Binary , join_binary) , (LowerExp , join_lower_exp) , (UpperExp , join_upper_exp) , }
        }
        pub use self::output::{PerLine, SpaceSep, StrSep};
    }
}

Submission Info

Judge Result