結果

問題 No.2930 Larger Mex
ユーザー naut3naut3
提出日時 2024-11-12 20:47:43
言語 Rust
(1.77.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 1 ms
6,820 KB
testcase_02 AC 1 ms
6,816 KB
testcase_03 AC 1 ms
6,816 KB
testcase_04 AC 2 ms
6,816 KB
testcase_05 AC 1 ms
6,820 KB
testcase_06 AC 1 ms
6,820 KB
testcase_07 AC 2 ms
6,816 KB
testcase_08 AC 40 ms
15,652 KB
testcase_09 AC 42 ms
14,764 KB
testcase_10 AC 42 ms
16,116 KB
testcase_11 AC 32 ms
13,604 KB
testcase_12 AC 53 ms
18,540 KB
testcase_13 AC 45 ms
17,064 KB
testcase_14 AC 56 ms
19,632 KB
testcase_15 AC 35 ms
16,312 KB
testcase_16 AC 36 ms
15,016 KB
testcase_17 AC 43 ms
17,752 KB
testcase_18 AC 34 ms
15,144 KB
testcase_19 AC 45 ms
17,468 KB
testcase_20 AC 46 ms
17,480 KB
testcase_21 AC 45 ms
17,656 KB
testcase_22 AC 52 ms
18,184 KB
testcase_23 AC 40 ms
15,412 KB
testcase_24 AC 42 ms
17,412 KB
testcase_25 AC 61 ms
19,216 KB
testcase_26 AC 43 ms
17,112 KB
testcase_27 AC 34 ms
13,672 KB
testcase_28 AC 39 ms
15,604 KB
testcase_29 AC 38 ms
15,516 KB
testcase_30 AC 33 ms
14,956 KB
testcase_31 AC 29 ms
13,124 KB
testcase_32 AC 39 ms
16,704 KB
testcase_33 AC 36 ms
16,048 KB
testcase_34 AC 42 ms
16,852 KB
testcase_35 AC 31 ms
11,800 KB
testcase_36 AC 37 ms
16,548 KB
testcase_37 AC 44 ms
16,708 KB
testcase_38 AC 45 ms
18,088 KB
testcase_39 AC 40 ms
17,612 KB
testcase_40 AC 42 ms
17,852 KB
testcase_41 AC 38 ms
15,656 KB
testcase_42 AC 36 ms
15,232 KB
testcase_43 AC 34 ms
14,576 KB
testcase_44 AC 39 ms
15,752 KB
testcase_45 AC 38 ms
15,544 KB
testcase_46 AC 9 ms
6,820 KB
testcase_47 AC 9 ms
6,816 KB
testcase_48 AC 7 ms
6,816 KB
testcase_49 AC 9 ms
6,816 KB
testcase_50 AC 33 ms
17,604 KB
testcase_51 AC 50 ms
18,364 KB
testcase_52 AC 61 ms
20,084 KB
権限があれば一括ダウンロードができます

ソースコード

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