#698321 (Rust) No.1675 Strange Minimum Query

提出ソース

結果

問題	No.1675 Strange Minimum Query
ユーザー	manta1130
提出日時	2021-09-10 22:31:31
言語	Rust (1.77.0)
結果	WA
実行時間	-
コード長	17,849 bytes
コンパイル時間	10,881 ms
コンパイル使用メモリ	176,068 KB
実行使用メモリ	14,000 KB
最終ジャッジ日時	2023-09-02 18:56:30
合計ジャッジ時間	19,054 ms
ジャッジサーバーID （参考情報）	judge13 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,368 KB
testcase_01	AC	1 ms 4,372 KB
testcase_02	AC	1 ms 4,368 KB
testcase_03	AC	428 ms 11,716 KB
testcase_04	AC	364 ms 9,860 KB
testcase_05	AC	28 ms 6,212 KB
testcase_06	AC	509 ms 13,268 KB
testcase_07	AC	517 ms 13,476 KB
testcase_08	AC	1 ms 4,368 KB
testcase_09	AC	3 ms 4,372 KB
testcase_10	AC	398 ms 12,268 KB
testcase_11	AC	31 ms 8,412 KB
testcase_12	AC	434 ms 12,824 KB
testcase_13	AC	331 ms 13,656 KB
testcase_14	AC	317 ms 13,688 KB
testcase_15	AC	314 ms 13,664 KB
testcase_16	AC	1 ms 4,372 KB
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-
testcase_33	WA	-
testcase_34	WA	-
testcase_35	WA	-
testcase_36	WA	-

権限があれば一括ダウンロードができます

コンパイルメッセージ

warning: unused imports: `BTreeMap`, `BinaryHeap`
 --> Main.rs:4:24
  |
4 | use std::collections::{BTreeMap, BinaryHeap};
  |                        ^^^^^^^^  ^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: 1 warning emitted

ソースコード

raw source code

#[allow(unused_imports)]
use std::io::{stdout, BufWriter, Write};

use std::collections::{BTreeMap, BinaryHeap};

fn main() {
    let out = stdout();
    let mut out = BufWriter::new(out.lock());

    inputv! {
        n:usize,q:usize
    }
    let mut query = vec![];
    let mut max = 0;
    for _ in 0..q {
        inputv! {
            l:usize,r:usize,b:u64
        }
        max = std::cmp::max(max, b);
        query.push((l - 1, r, b));
    }
    let qc = query.clone();
    query.sort_by_key(|q| std::cmp::Reverse(q.2));

    let mut ans = vec![max; n];
    let mut mex = Mex::new();

    for (l, r, b) in query {
        let idx = mex.mex(l as i64, r as i64).unwrap_or(l as i64);
        ans[idx as usize] = b;
        mex.insert_range(l as i64, r as i64);
    }

    let sg: Segtree<Min<_>> = ans.clone().into();
    let mut flag = true;
    for (l, r, b) in qc {
        if sg.prod(l, r) != b {
            flag = false;
            break;
        }
    }
    //dbg!(&ans);
    if !flag {
        writeln!(out, "-1").unwrap();
    } else {
        for i in 0..n {
            if i == n - 1 {
                writeln!(out, "{}", ans[i]).unwrap();
            } else {
                write!(out, "{} ", ans[i]).unwrap();
            }
        }
    }
}

//https://github.com/rust-lang-ja/ac-library-rs
//https://github.com/manta1130/competitive-template-rs

use input::*;
use mex::*;
use segtree::*;

pub mod input {
    use std::cell::RefCell;
    use std::io;
    pub const SPLIT_DELIMITER: char = ' ';
    pub use std::io::prelude::*;

    thread_local! {
        pub static INPUT_BUFFER:RefCell<std::collections::VecDeque<String>>=RefCell::new(std::collections::VecDeque::new());
    }

    #[macro_export]
    macro_rules! input_internal {
        ($x:ident : $t:ty) => {
            INPUT_BUFFER.with(|p| {
                if p.borrow().len() == 0 {
                    let temp_str = input_line_str();
                    let mut split_result_iter = temp_str
                        .split(SPLIT_DELIMITER)
                        .map(|q| q.to_string())
                        .collect::<std::collections::VecDeque<_>>();
                    p.borrow_mut().append(&mut split_result_iter)
                }
            });
            let mut buf_split_result = String::new();
            INPUT_BUFFER.with(|p| buf_split_result = p.borrow_mut().pop_front().unwrap());
            let $x: $t = buf_split_result.parse().unwrap();
        };
        (mut $x:ident : $t:ty) => {
            INPUT_BUFFER.with(|p| {
                if p.borrow().len() == 0 {
                    let temp_str = input_line_str();
                    let mut split_result_iter = temp_str
                        .split(SPLIT_DELIMITER)
                        .map(|q| q.to_string())
                        .collect::<std::collections::VecDeque<_>>();
                    p.borrow_mut().append(&mut split_result_iter)
                }
            });
            let mut buf_split_result = String::new();
            INPUT_BUFFER.with(|p| buf_split_result = p.borrow_mut().pop_front().unwrap());
            let mut $x: $t = buf_split_result.parse().unwrap();
        };
    }

    pub fn input_buffer_is_empty() -> bool {
        let mut empty = false;
        INPUT_BUFFER.with(|p| {
            if p.borrow().len() == 0 {
                empty = true;
            }
        });
        empty
    }

    #[macro_export]
    macro_rules! inputv {
    ($i:ident : $t:ty) => {
        input_internal!{$i : $t}
    };
    (mut $i:ident : $t:ty) => {
        input_internal!{mut $i : $t}
    };
    ($i:ident : $t:ty $(,)*) => {
            input_internal!{$i : $t}
    };
    (mut $i:ident : $t:ty $(,)*) => {
            input_internal!{mut $i : $t}
    };
    (mut $i:ident : $t:ty,$($q:tt)*) => {
            input_internal!{mut $i : $t}
            inputv!{$($q)*}
    };
    ($i:ident : $t:ty,$($q:tt)*) => {
            input_internal!{$i : $t}
            inputv!{$($q)*}
    };
}

    pub fn input_all() {
        INPUT_BUFFER.with(|p| {
            if p.borrow().len() == 0 {
                let mut temp_str = String::new();
                std::io::stdin().read_to_string(&mut temp_str).unwrap();
                let mut split_result_iter = temp_str
                    .split_whitespace()
                    .map(|q| q.to_string())
                    .collect::<std::collections::VecDeque<_>>();
                p.borrow_mut().append(&mut split_result_iter)
            }
        });
    }

    pub fn input_line_str() -> String {
        let mut s = String::new();
        io::stdin().read_line(&mut s).unwrap();
        s.trim().to_string()
    }

    #[allow(clippy::match_wild_err_arm)]
    pub fn input_vector<T>() -> Vec<T>
    where
        T: std::str::FromStr,
    {
        let mut v: Vec<T> = Vec::new();

        let s = input_line_str();
        let split_result = s.split(SPLIT_DELIMITER);
        for z in split_result {
            let buf = match z.parse() {
                Ok(r) => r,
                Err(_) => panic!("Parse Error",),
            };
            v.push(buf);
        }
        v
    }

    #[allow(clippy::match_wild_err_arm)]
    pub fn input_vector_row<T>(n: usize) -> Vec<T>
    where
        T: std::str::FromStr,
    {
        let mut v = Vec::with_capacity(n);
        for _ in 0..n {
            let buf = match input_line_str().parse() {
                Ok(r) => r,
                Err(_) => panic!("Parse Error",),
            };
            v.push(buf);
        }
        v
    }

    pub trait ToCharVec {
        fn to_charvec(&self) -> Vec<char>;
    }

    impl ToCharVec for String {
        fn to_charvec(&self) -> Vec<char> {
            self.to_string().chars().collect::<Vec<_>>()
        }
    }
}
pub mod internal_bit {

    #[allow(dead_code)]
    pub(crate) fn ceil_pow2(n: u32) -> u32 {
        32 - n.saturating_sub(1).leading_zeros()
    }
}
pub mod internal_type_traits {
    use std::{
        fmt,
        iter::{Product, Sum},
        ops::{
            Add, AddAssign, BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Div,
            DivAssign, Mul, MulAssign, Not, Rem, RemAssign, Shl, ShlAssign, Shr, ShrAssign, Sub,
            SubAssign,
        },
    };

    pub trait Integral:
        'static
        + Send
        + Sync
        + Copy
        + Ord
        + Not<Output = Self>
        + Add<Output = Self>
        + Sub<Output = Self>
        + Mul<Output = Self>
        + Div<Output = Self>
        + Rem<Output = Self>
        + AddAssign
        + SubAssign
        + MulAssign
        + DivAssign
        + RemAssign
        + Sum
        + Product
        + BitOr<Output = Self>
        + BitAnd<Output = Self>
        + BitXor<Output = Self>
        + BitOrAssign
        + BitAndAssign
        + BitXorAssign
        + Shl<Output = Self>
        + Shr<Output = Self>
        + ShlAssign
        + ShrAssign
        + fmt::Display
        + fmt::Debug
        + fmt::Binary
        + fmt::Octal
        + Zero
        + One
        + BoundedBelow
        + BoundedAbove
    {
    }

    pub trait Zero {
        fn zero() -> Self;
    }

    pub trait One {
        fn one() -> Self;
    }

    pub trait BoundedBelow {
        fn min_value() -> Self;
    }

    pub trait BoundedAbove {
        fn max_value() -> Self;
    }

    macro_rules! impl_integral {
    ($($ty:ty),*) => {
        $(
            impl Zero for $ty {
                #[inline]
                fn zero() -> Self {
                    0
                }
            }

            impl One for $ty {
                #[inline]
                fn one() -> Self {
                    1
                }
            }

            impl BoundedBelow for $ty {
                #[inline]
                fn min_value() -> Self {
                    Self::min_value()
                }
            }

            impl BoundedAbove for $ty {
                #[inline]
                fn max_value() -> Self {
                    Self::max_value()
                }
            }

            impl Integral for $ty {}
        )*
    };
}

    impl_integral!(i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize);
}
pub mod mex {
    use std::collections::BTreeSet;

    type ValueType = i64;

    pub struct Mex {
        set: BTreeSet<(ValueType, ValueType)>,
    }

    impl Default for Mex {
        fn default() -> Self {
            Self::new()
        }
    }

    impl Mex {
        pub fn new() -> Self {
            let mut set = BTreeSet::new();
            set.insert((ValueType::min_value(), ValueType::min_value()));
            set.insert((ValueType::max_value(), ValueType::max_value()));
            Mex { set }
        }

        pub fn insert(&mut self, x: ValueType) {
            let back = *self
                .set
                .range(..(x, ValueType::max_value()))
                .next_back()
                .unwrap();
            let next = *self
                .set
                .range((x + 1, ValueType::min_value())..)
                .next()
                .unwrap();

            if back.1 == x && x + 1 == next.0 {
                self.set.remove(&back);
                self.set.remove(&next);
                self.set.insert((back.0, next.1));
            } else if back.1 == x {
                self.set.remove(&back);
                self.set.insert((back.0, x + 1));
            } else if x + 1 == next.0 {
                self.set.remove(&next);
                self.set.insert((x, next.1));
            } else {
                self.set.insert((x, x + 1));
            }
        }

        pub fn insert_range(&mut self, f: i64, t: i64) {
            let left = self.mex(f - 1, f).is_some();
            let right = self.mex(t, t + 1).is_some();

            self.remove(f - 1);
            self.remove(t);

            self.remove_range(f, t);
            self.set.insert((f, t));

            if left {
                self.insert(f - 1);
            }
            if right {
                self.insert(t);
            }
        }
        pub fn remove_range(&mut self, f: i64, t: i64) {
            let left = self.mex(f - 1, f).is_some();
            let right = self.mex(t, t + 1).is_some();

            self.insert(f);
            self.insert(t - 1);
            self.remove(f - 1);
            self.remove(t);

            let remove_list = self
                .set
                .range((f, f)..=(t - 1, t))
                .cloned()
                .collect::<Vec<_>>();

            for k in remove_list {
                self.set.remove(&k);
            }
            if left {
                self.insert(f - 1);
            }
            if right {
                self.insert(t);
            }
        }

        pub fn remove(&mut self, x: ValueType) {
            let back = *self
                .set
                .range(..(x, ValueType::max_value()))
                .next_back()
                .unwrap();

            if back.1 > x {
                self.set.remove(&back);
                self.set.insert((back.0, x));
                self.set.insert((x + 1, back.1));
            }
        }

        pub fn mex(&mut self, f: ValueType, t: ValueType) -> Option<ValueType> {
            if f >= t {
                return None;
            }

            let r = self
                .set
                .range(..(f, ValueType::max_value()))
                .next_back()
                .unwrap()
                .1;

            if r >= t {
                None
            } else {
                Some(std::cmp::max(r, f))
            }
        }
    }
}
pub mod segtree {
    use crate::internal_bit::ceil_pow2;
    use crate::internal_type_traits::{BoundedAbove, BoundedBelow, One, Zero};
    use std::cmp::{max, min};
    use std::convert::Infallible;
    use std::marker::PhantomData;
    use std::ops::{Add, Mul};

    pub trait Monoid {
        type S: Clone;
        fn identity() -> Self::S;
        fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S;
    }

    pub struct Max<S>(Infallible, PhantomData<fn() -> S>);
    impl<S> Monoid for Max<S>
    where
        S: Copy + Ord + BoundedBelow,
    {
        type S = S;
        fn identity() -> Self::S {
            S::min_value()
        }
        fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
            max(*a, *b)
        }
    }

    pub struct Min<S>(Infallible, PhantomData<fn() -> S>);
    impl<S> Monoid for Min<S>
    where
        S: Copy + Ord + BoundedAbove,
    {
        type S = S;
        fn identity() -> Self::S {
            S::max_value()
        }
        fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
            min(*a, *b)
        }
    }

    pub struct Additive<S>(Infallible, PhantomData<fn() -> S>);
    impl<S> Monoid for Additive<S>
    where
        S: Copy + Add<Output = S> + Zero,
    {
        type S = S;
        fn identity() -> Self::S {
            S::zero()
        }
        fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
            *a + *b
        }
    }

    pub struct Multiplicative<S>(Infallible, PhantomData<fn() -> S>);
    impl<S> Monoid for Multiplicative<S>
    where
        S: Copy + Mul<Output = S> + One,
    {
        type S = S;
        fn identity() -> Self::S {
            S::one()
        }
        fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
            *a * *b
        }
    }

    impl<M: Monoid> Default for Segtree<M> {
        fn default() -> Self {
            Segtree::new(0)
        }
    }
    impl<M: Monoid> Segtree<M> {
        pub fn new(n: usize) -> Segtree<M> {
            vec![M::identity(); n].into()
        }
    }
    impl<M: Monoid> From<Vec<M::S>> for Segtree<M> {
        fn from(v: Vec<M::S>) -> Self {
            let n = v.len();
            let log = ceil_pow2(n as u32) as usize;
            let size = 1 << log;
            let mut d = vec![M::identity(); 2 * size];
            d[size..(size + n)].clone_from_slice(&v);
            let mut ret = Segtree { n, size, log, d };
            for i in (1..size).rev() {
                ret.update(i);
            }
            ret
        }
    }
    impl<M: Monoid> Segtree<M> {
        pub fn set(&mut self, mut p: usize, x: M::S) {
            assert!(p < self.n);
            p += self.size;
            self.d[p] = x;
            for i in 1..=self.log {
                self.update(p >> i);
            }
        }

        pub fn get(&self, p: usize) -> M::S {
            assert!(p < self.n);
            self.d[p + self.size].clone()
        }

        pub fn prod(&self, mut l: usize, mut r: usize) -> M::S {
            assert!(l <= r && r <= self.n);
            let mut sml = M::identity();
            let mut smr = M::identity();
            l += self.size;
            r += self.size;

            while l < r {
                if l & 1 != 0 {
                    sml = M::binary_operation(&sml, &self.d[l]);
                    l += 1;
                }
                if r & 1 != 0 {
                    r -= 1;
                    smr = M::binary_operation(&self.d[r], &smr);
                }
                l >>= 1;
                r >>= 1;
            }

            M::binary_operation(&sml, &smr)
        }

        pub fn all_prod(&self) -> M::S {
            self.d[1].clone()
        }

        pub fn max_right<F>(&self, mut l: usize, f: F) -> usize
        where
            F: Fn(&M::S) -> bool,
        {
            assert!(l <= self.n);
            assert!(f(&M::identity()));
            if l == self.n {
                return self.n;
            }
            l += self.size;
            let mut sm = M::identity();
            while {
                while l % 2 == 0 {
                    l >>= 1;
                }
                if !f(&M::binary_operation(&sm, &self.d[l])) {
                    while l < self.size {
                        l *= 2;
                        let res = M::binary_operation(&sm, &self.d[l]);
                        if f(&res) {
                            sm = res;
                            l += 1;
                        }
                    }
                    return l - self.size;
                }
                sm = M::binary_operation(&sm, &self.d[l]);
                l += 1;
                {
                    let l = l as isize;
                    (l & -l) != l
                }
            } {}
            self.n
        }

        pub fn min_left<F>(&self, mut r: usize, f: F) -> usize
        where
            F: Fn(&M::S) -> bool,
        {
            assert!(r <= self.n);
            assert!(f(&M::identity()));
            if r == 0 {
                return 0;
            }
            r += self.size;
            let mut sm = M::identity();
            while {
                r -= 1;
                while r > 1 && r % 2 == 1 {
                    r >>= 1;
                }
                if !f(&M::binary_operation(&self.d[r], &sm)) {
                    while r < self.size {
                        r = 2 * r + 1;
                        let res = M::binary_operation(&self.d[r], &sm);
                        if f(&res) {
                            sm = res;
                            r -= 1;
                        }
                    }
                    return r + 1 - self.size;
                }
                sm = M::binary_operation(&self.d[r], &sm);
                {
                    let r = r as isize;
                    (r & -r) != r
                }
            } {}
            0
        }

        fn update(&mut self, k: usize) {
            self.d[k] = M::binary_operation(&self.d[2 * k], &self.d[2 * k + 1]);
        }
    }

    pub struct Segtree<M>
    where
        M: Monoid,
    {
        n: usize,
        size: usize,
        log: usize,
        d: Vec<M::S>,
    }
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード