結果

問題 No.2930 Larger Mex
ユーザー naut3
提出日時 2024-11-12 20:47:43
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 61 ms / 2,000 ms
コード長 6,303 bytes
コンパイル時間 13,886 ms
コンパイル使用メモリ 402,900 KB
実行使用メモリ 20,084 KB
最終ジャッジ日時 2024-11-12 20:48:04
合計ジャッジ時間 19,780 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(non_snake_case, unused_must_use, unused_imports)]
use std::io::{self, prelude::*};

fn main() {
    let (stdin, stdout) = (io::read_to_string(io::stdin()).unwrap(), io::stdout());
    let (mut stdin, mut buffer) = (stdin.split_whitespace(), io::BufWriter::new(stdout.lock()));

    macro_rules! input {
        ($t: tt, $n: expr) => {
            (0..$n).map(|_| input!($t)).collect::<Vec<_>>()
        };
        (Chars) => {
            input!(String).chars().collect::<Vec<_>>()
        };
        (Usize1) => {
            stdin.next().unwrap().parse::<usize>().unwrap() - 1
        };
        ($t: ty) => {
            stdin.next().unwrap().parse::<$t>().unwrap()
        };
    }

    let N = input!(usize);
    let M = input!(usize);

    if M == 0 {
        for i in (1..=N).rev() {
            writeln!(buffer, "{}", i);
        }
        return;
    }

    let A = input!(usize, N);

    let mut positions: segtree::SegmentTree<algebra::Max<usize>> =
        segtree::SegmentTree::from(&vec![usize::MAX; M]);
    let mut cs = vec![0; N + 1];

    for i in (0..N).rev() {
        let a = A[i];

        if a < M {
            positions.insert(a, i);
        }

        let r = positions.prod(0..M);

        if r != usize::MAX {
            cs[r - i] += 1;
            cs[N - i] -= 1;
        }
    }

    let mut ans = vec![cs[0]];

    for i in 1..N {
        ans.push(ans[i - 1] + cs[i]);
    }

    writeln!(
        buffer,
        "{}",
        ans.iter()
            .map(|x| x.to_string())
            .collect::<Vec<_>>()
            .join("\n")
    );
}

#[rustfmt::skip]
pub mod segtree {use crate::algebra::Monoid;pub struct SegmentTree<M: Monoid> { size: usize, tree: Vec<M::S>,}impl<M: Monoid> SegmentTree<M> { pub fn new(size: usize) -> Self { Self { size, tree: vec![M::E; size << 1], } } pub fn from(array: &[M::S]) -> Self { let size = array.len(); let tree = { let mut tree = vec![M::E; size]; tree.append(&mut array.to_vec()); for i in (1..size).rev() { tree[i] = M::op(&tree[i << 1], &tree[i << 1 | 1]); } tree }; return Self { size, tree }; } pub fn insert(&mut self, mut i: usize, s: M::S) { assert!(i < self.size); i += self.size; self.tree[i] = s; while i > 1 { i >>= 1; self.tree[i] = M::op(&self.tree[i << 1], &self.tree[i << 1 | 1]); } } pub fn get(&self, i: usize) -> M::S { assert!(i < self.size); self.tree[i + self.size].clone() } pub fn prod<R: std::ops::RangeBounds<usize>>(&self, range: R) -> M::S { let left = match range.start_bound() { std::ops::Bound::Included(&l) => l, std::ops::Bound::Excluded(&l) => l + 1, std::ops::Bound::Unbounded => 0, }; let right = match range.end_bound() { std::ops::Bound::Included(&r) => r + 1, std::ops::Bound::Excluded(&r) => r, std::ops::Bound::Unbounded => self.size, }; return self._prod(left, right); } fn _prod(&self, mut left: usize, mut right: usize) -> M::S { left += self.size; right += self.size; let (mut sl, mut sr) = (M::E, M::E); while left < right { if left & 1 == 1 { sl = M::op(&sl, &self.tree[left]); left += 1; } if right & 1 == 1 { right ^= 1; sr = M::op(&self.tree[right], &sr); } left >>= 1; right >>= 1; } return M::op(&sl, &sr); }}impl<M: Monoid> std::ops::Index<usize> for SegmentTree<M> { type Output = M::S; fn index(&self, index: usize) -> &Self::Output { &self.tree[index + self.size] }}impl<M: Monoid<S = S>, S: std::fmt::Display> std::fmt::Display for SegmentTree<M> { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!( f, "{}", (0..self.size) .map(|i| self.get(i)) .collect::<Vec<_>>() .iter() .map(|x| x.to_string()) .collect::<Vec<_>>() .join(" ") ) }}}
#[rustfmt::skip]
pub mod algebra {pub trait SemiGroup { type S; fn op(lhs: &Self::S, rhs: &Self::S) -> Self::S;}pub trait Band { type S; fn op(lhs: &Self::S, rhs: &Self::S) -> Self::S;}pub trait Monoid { type S: Clone + PartialEq + Eq; fn op(lhs: &Self::S, rhs: &Self::S) -> Self::S; const E: Self::S;}pub struct Min<T> { _marker: std::marker::PhantomData<T>,}pub struct Max<T> { _marker: std::marker::PhantomData<T>,}pub struct Add<T> { _marker: std::marker::PhantomData<T>,}pub struct Mul<T> { _marker: std::marker::PhantomData<T>,}pub struct BitAnd<T> { _marker: std::marker::PhantomData<T>,}pub struct BitOr<T> { _marker: std::marker::PhantomData<T>,}pub struct BitXor<T> { _marker: std::marker::PhantomData<T>,}macro_rules! impl_to_integers { ($($t: ty), *) => { $( impl SemiGroup for Min<$t> { type S = $t; fn op(lhs: &$t, rhs: &$t) -> $t { std::cmp::min(*lhs, *rhs) } } impl SemiGroup for Max<$t> { type S = $t; fn op(lhs: &$t, rhs: &$t) -> $t { std::cmp::max(*lhs, *rhs) } } impl SemiGroup for Add<$t> { type S = $t; fn op(lhs: &$t, rhs: &$t) -> $t { lhs + rhs } } impl SemiGroup for Mul<$t> { type S = $t; fn op(lhs: &$t, rhs: &$t) -> $t { lhs * rhs } } impl SemiGroup for BitAnd<$t> { type S = $t; fn op(lhs: &$t, rhs: &$t) -> $t { lhs & rhs } } impl SemiGroup for BitOr<$t> { type S = $t; fn op(lhs: &$t, rhs: &$t) -> $t { lhs | rhs } } impl SemiGroup for BitXor<$t> { type S = $t; fn op(lhs: &$t, rhs: &$t) -> $t { lhs ^ rhs } } impl Band for Min<$t> { type S = $t; fn op(lhs: &$t, rhs: &$t) -> $t { std::cmp::min(*lhs, *rhs) } } impl Band for Max<$t> { type S = $t; fn op(lhs: &$t, rhs: &$t) -> $t { std::cmp::max(*lhs, *rhs) } } impl Band for BitAnd<$t> { type S = $t; fn op(lhs: &$t, rhs: &$t) -> $t { lhs & rhs } } impl Band for BitOr<$t> { type S = $t; fn op(lhs: &$t, rhs: &$t) -> $t { lhs | rhs } } impl Monoid for Min<$t> { type S = $t; fn op(lhs: &$t, rhs: &$t) -> $t { std::cmp::min(*lhs, *rhs) } const E: $t = <$t>::MAX; } impl Monoid for Max<$t> { type S = $t; fn op(lhs: &$t, rhs: &$t) -> $t { std::cmp::max(*lhs, *rhs) } const E: $t = <$t>::MIN; } impl Monoid for Add<$t> { type S = $t; fn op(lhs: &$t, rhs: &$t) -> $t { lhs + rhs } const E: $t = 0; } impl Monoid for Mul<$t> { type S = $t; fn op(lhs: &$t, rhs: &$t) -> $t { lhs * rhs } const E: $t = 1; } impl Monoid for BitAnd<$t> { type S = $t; fn op(lhs: &$t, rhs: &$t) -> $t { lhs & rhs } const E: $t = <$t>::MAX; } impl Monoid for BitOr<$t> { type S = $t; fn op(lhs: &$t, rhs: &$t) -> $t { lhs | rhs } const E: $t = 0; } impl Monoid for BitXor<$t> { type S = $t; fn op(lhs: &$t, rhs: &$t) -> $t { lhs ^ rhs } const E: $t = 0; } )* };}impl_to_integers!(u8, u16, u32, u64, u128, usize, i8, i16, i32, i64, i128, isize);}
0