#669693 (Rust) No.1557 Binary Variable

• 問題: No.1557 Binary Variable
• ユーザー: へのく
• 提出日時: 2021-06-25 22:07:28
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 59 ms / 2,000 ms
• コード長: 8,707 bytes
• コンパイル時間: 18,377 ms
• コンパイル使用メモリ: 404,140 KB
• 実行使用メモリ: 6,944 KB
• 最終ジャッジ日時: 2024-06-25 08:28:31
• 合計ジャッジ時間: 15,868 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	30 ms; 6,812 KB
testcase_01	AC	41 ms; 6,816 KB
testcase_02	AC	1 ms; 6,940 KB
testcase_03	AC	1 ms; 6,944 KB
testcase_04	AC	37 ms; 6,940 KB
testcase_05	AC	36 ms; 6,940 KB
testcase_06	AC	35 ms; 6,940 KB
testcase_07	AC	35 ms; 6,944 KB
testcase_08	AC	39 ms; 6,944 KB
testcase_09	AC	40 ms; 6,944 KB
testcase_10	AC	44 ms; 6,940 KB
testcase_11	AC	44 ms; 6,944 KB
testcase_12	AC	38 ms; 6,944 KB
testcase_13	AC	44 ms; 6,940 KB
testcase_14	AC	47 ms; 6,940 KB
testcase_15	AC	46 ms; 6,940 KB
testcase_16	AC	46 ms; 6,940 KB
testcase_17	AC	46 ms; 6,944 KB
testcase_18	AC	47 ms; 6,944 KB
testcase_19	AC	49 ms; 6,944 KB
testcase_20	AC	48 ms; 6,940 KB
testcase_21	AC	48 ms; 6,944 KB
testcase_22	AC	48 ms; 6,940 KB
testcase_23	AC	48 ms; 6,944 KB
testcase_24	AC	50 ms; 6,944 KB
testcase_25	AC	50 ms; 6,944 KB
testcase_26	AC	49 ms; 6,944 KB
testcase_27	AC	51 ms; 6,940 KB
testcase_28	AC	50 ms; 6,944 KB
testcase_29	AC	56 ms; 6,940 KB
testcase_30	AC	55 ms; 6,944 KB
testcase_31	AC	59 ms; 6,940 KB
testcase_32	AC	56 ms; 6,940 KB
testcase_33	AC	48 ms; 6,940 KB
testcase_34	AC	1 ms; 6,944 KB
testcase_35	AC	1 ms; 6,940 KB
testcase_36	AC	1 ms; 6,944 KB

ソースコード

#![allow(non_snake_case)]
use crate::{arraylist::List, scanner::Scanner};

fn main() {
    let mut scan = Scanner::new();
    let n = scan.long();
    let m = scan.int();
    let mut lr = List::gen(m, |_| (scan.long() - 1, scan.long() - 1));
    lr.sort_by_key(|t| t.1);
    let mut cnt = 0;
    let mut x = -1;
    for &(l, r) in &lr {
        if x < l {
            x = r;
            cnt += 1;
        }
    }
    println!("{}", n - cnt);
}

pub mod scanner {
    use std::io::{stdin, BufReader, Bytes, Read, Stdin};
    use std::str::FromStr;

    pub struct Scanner {
        buf: Bytes<BufReader<Stdin>>,
    }

    impl Scanner {
        pub fn new() -> Scanner {
            Scanner {
                buf: BufReader::new(stdin()).bytes(),
            }
        }

        #[inline]
        fn token<T: std::iter::FromIterator<char>>(&mut self) -> T {
            self.buf
                .by_ref()
                .map(|c| c.unwrap() as char)
                .skip_while(|c| c.is_whitespace())
                .take_while(|c| !c.is_whitespace())
                .collect()
        }

        #[inline]
        pub fn read<T: FromStr>(&mut self) -> T {
            self.string().parse().ok().unwrap()
        }

        #[inline]
        pub fn string(&mut self) -> String {
            self.token()
        }

        #[inline]
        pub fn int(&mut self) -> isize {
            self.read()
        }

        #[inline]
        pub fn long(&mut self) -> i64 {
            self.read()
        }
    }
}
pub mod arraylist {

    use std::ops::*;
    use std::slice::Iter;

    use std::fmt::Formatter;
    use std::iter::FromIterator;

    #[derive(Clone, PartialEq, Eq, PartialOrd, Ord)]
    pub struct List<T> {
        pub data: Vec<T>,
    }

    impl<T> List<T> {
        #[inline]
        pub fn gen<'a, S>(n: isize, f: S) -> List<T>
        where
            S: FnMut(isize) -> T + 'a,
        {
            (0..n).map(f).collect()
        }
    }

    macro_rules! impl_idx {
        ($($tpe:ty, $t:ident [$($output:tt)+], $slf:ident, $index:ident, $f:expr),*) => {
            $(impl<$t> Index<$tpe> for List<$t> {
                type Output = $($output)+;
                #[inline]
                fn index(&$slf, $index: $tpe) -> &Self::Output {$f}
            })*
            $(impl<$t> Index<$tpe> for lst<$t> {
                type Output = $($output)+;
                #[inline]
                fn index(&$slf, $index: $tpe) -> &Self::Output {$f}
            })*
        }
    }

    macro_rules! impl_idx_mut {
        ($($tpe:ty, $slf:ident, $index:ident, $f:expr),*) => {
            $(impl<T> IndexMut<$tpe> for List<T> {
                #[inline]
                fn index_mut(&mut $slf, $index: $tpe) -> &mut Self::Output {$f}
            })*
            $(impl<T> IndexMut<$tpe> for lst<T> {
                #[inline]
                fn index_mut(&mut $slf, $index: $tpe) -> &mut Self::Output {$f}
            })*
        };
    }

    macro_rules! impl_idx_slice {
        ($($tpe:ty),*) => {
            impl_idx!($($tpe, T [lst<T>], self, i, self.as_slice(i)),*);
            impl_idx_mut!($($tpe, self, i, self.as_slice_mut(i)),*);
        };
    }

    impl_idx! {
        isize, T [T], self, i, self.at(i),
        char, T [T], self, i, self.at(i as isize - 'a' as isize)
    }

    impl_idx_slice! {
        Range<isize>, RangeTo<isize>, RangeFrom<isize>, RangeFull, RangeInclusive<isize>, RangeToInclusive<isize>
    }

    impl_idx_mut! {
        isize, self, i, self.at_mut(i),
        char, self, i, self.at_mut(i as isize - 'a' as isize)
    }

    impl<T> FromIterator<T> for List<T> {
        #[inline]
        fn from_iter<U: IntoIterator<Item = T>>(iter: U) -> Self {
            List {
                data: iter.into_iter().collect(),
            }
        }
    }

    impl<T> IntoIterator for List<T> {
        type Item = T;
        type IntoIter = std::vec::IntoIter<T>;

        #[inline]
        fn into_iter(self) -> std::vec::IntoIter<T> {
            self.data.into_iter()
        }
    }

    macro_rules! impl_traits {
        ($($tpe:tt),*) => {
            $(
                impl<T: std::fmt::Display> std::fmt::Display for $tpe<T> {
                    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
                        write!(f, "{}", self.iter().map(|x| format!("{}", x)).collect::<Vec<_>>().join(" "))
                    }
                }

                impl<T: std::fmt::Debug> std::fmt::Debug for $tpe<T> {
                    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
                        self.data.fmt(f)
                    }
                }

                impl<'a, T> IntoIterator for &'a $tpe<T> {
                    type Item = &'a T;
                    type IntoIter = Iter<'a, T>;

                    #[inline]
                    fn into_iter(self) -> Iter<'a, T> {
                        self.iter()
                    }
                }
            )*
        };
    }

    impl_traits!(List, lst);

    impl<T> From<Vec<T>> for List<T> {
        #[inline]
        fn from(vec: Vec<T>) -> Self {
            List { data: vec }
        }
    }

    impl<T: Clone> From<&[T]> for List<T> {
        #[inline]
        fn from(slice: &[T]) -> Self {
            slice.iter().cloned().collect()
        }
    }

    impl<T> Deref for List<T> {
        type Target = lst<T>;

        #[inline]
        fn deref(&self) -> &lst<T> {
            lst::new(&self.data)
        }
    }

    impl<T> DerefMut for List<T> {
        #[inline]
        fn deref_mut(&mut self) -> &mut lst<T> {
            lst::new_mut(&mut self.data)
        }
    }

    #[macro_export]
    macro_rules! list {
        () => { $crate::arraylist::List::new() };
        ($($v:expr),+ $(,)?) => { $crate::arraylist::List::from([$($v),+].to_vec()) };
        ($v:expr; $a:expr) => { $crate::arraylist::List::init($v, $a)};
        ($v:expr; $a:expr; $($rest:expr);+) => { $crate::arraylist::List::init(list!($v; $($rest);+), $a) };
    }

    #[allow(non_camel_case_types)]
    #[derive(PartialEq, Eq, PartialOrd, Ord)]
    #[repr(transparent)]
    pub struct lst<T> {
        data: [T],
    }

    impl<T> lst<T> {
        #[inline]
        pub fn new(slice: &[T]) -> &Self {
            unsafe { &*(slice as *const [T] as *const Self) }
        }
        #[inline]
        pub fn new_mut(slice: &mut [T]) -> &mut Self {
            unsafe { &mut *(slice as *mut [T] as *mut Self) }
        }

        #[inline]
        fn at(&self, index: isize) -> &T {
            if cfg!(debug_assertions) {
                self.data.index(index as usize)
            } else {
                unsafe { self.data.get_unchecked(index as usize) }
            }
        }
        #[inline]
        fn at_mut(&mut self, index: isize) -> &mut T {
            if cfg!(debug_assertions) {
                self.data.index_mut(index as usize)
            } else {
                unsafe { self.data.get_unchecked_mut(index as usize) }
            }
        }
        #[inline]
        pub fn as_slice(&self, range: impl RangeBounds<isize>) -> &lst<T> {
            if cfg!(debug_assertions) {
                lst::new(self.data.index(self.rgm(range)))
            } else {
                unsafe { lst::new(self.data.get_unchecked(self.rgm(range))) }
            }
        }
        #[inline]
        pub fn as_slice_mut(&mut self, range: impl RangeBounds<isize>) -> &mut lst<T> {
            if cfg!(debug_assertions) {
                lst::new_mut(self.data.index_mut(self.rgm(range)))
            } else {
                let r = self.rgm(range);
                unsafe { lst::new_mut(self.data.get_unchecked_mut(r)) }
            }
        }

        #[inline]
        fn rgm(&self, r: impl RangeBounds<isize>) -> Range<usize> {
            (match r.start_bound() {
                Bound::Included(x) => *x as usize,
                Bound::Excluded(x) => *x as usize + 1,
                _ => 0,
            })
            .max(0)..(match r.end_bound() {
                Bound::Included(x) => *x as usize + 1,
                Bound::Excluded(x) => *x as usize,
                _ => self.len(),
            })
            .min(self.len())
        }
    }

    impl lst<isize> {}

    impl<T> Deref for lst<T> {
        type Target = [T];
        #[inline]
        fn deref(&self) -> &[T] {
            &self.data
        }
    }

    impl<T> DerefMut for lst<T> {
        #[inline]
        fn deref_mut(&mut self) -> &mut [T] {
            &mut self.data
        }
    }

    impl<'a, T> From<&'a [T]> for &'a lst<T> {
        #[inline]
        fn from(slice: &'a [T]) -> Self {
            lst::new(slice)
        }
    }
}