結果
| 問題 | No.1557 Binary Variable |
| ユーザー |
 へのく
|
| 提出日時 | 2021-06-25 22:07:28 |
| 言語 | Rust (1.83.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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 34 |
ソースコード
#![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)
}
}
}