#290098 (Rust) No.743 Segments on a Polygon

• 問題: No.743 Segments on a Polygon
• ユーザー: くれちー
• 提出日時: 2018-10-05 22:40:40
• 言語: Rust (1.77.0 + proconio)
• 結果: CE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 15,457 bytes
• コンパイル時間: 12,964 ms
• コンパイル使用メモリ: 388,804 KB
• 最終ジャッジ日時: 2024-11-14 20:39:10
• 合計ジャッジ時間: 13,685 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

コンパイルメッセージ

error: expected one of `!`, `(`, `...`, `..=`, `..`, `::`, `:`, `{`, or `|`, found `)`
   --> src/main.rs:215:36
    |
215 |         fn invert(&Self::Underlying) -> Self::Underlying;
    |                                    ^ expected one of 9 possible tokens
    |
    = note: anonymous parameters are removed in the 2018 edition (see RFC 1685)
help: explicitly ignore the parameter name
    |
215 |         fn invert(_: &Self::Underlying) -> Self::Underlying;
    |                   ~~~~~~~~~~~~~~~~~~~~

error: `$op_rhs:pat` is followed by `|`, which is not allowed for `pat` fragments
 --> src/main.rs:2:45
  |
2 |   ($T:ty, $U:ty, | $op_lhs:pat, $op_rhs:pat | $op_ret:expr) => {
  |                                 ----------- ^ not allowed after `pat` fragments
  |                                 |
  |                                 help: try a `pat_param` fragment specifier instead: `$op_rhs:pat_param`
  |
  = note: allowed there are: `=>`, `,`, `=`, `if` or `in`

error: `$inv_x:pat` is followed by `|`, which is not allowed for `pat` fragments
  --> src/main.rs:24:24
   |
24 |   ($T:ty, | $inv_x:pat | $inv_b:expr) => {
   |             ---------- ^ not allowed after `pat` fragments
   |             |
   |             help: try a `pat_param` fragment specifier instead: `$inv_x:pat_param`
   |
   = note: allowed there are: `=>`, `,`, `=`, `if` or `in`

error: `$op_r:pat` is followed by `|`, which is not allowed for `pat` fragments
   --> src/main.rs:270:47
    |
270 |         ($t:ty, $u:ty, | $op_l:pat, $op_r:pat | $op_b:expr, $id:expr) => {
    |                                     --------- ^ not allowed after `pat` fragments
    |                                     |
    |                                     help: try a `pat_param` fragment specifier instead: `$op_r:pat_param`
    |
    = note: allowed there are: `=>`, `,`, `=`, `if` or `in`

error: `$op_r:pat` is followed by `|`, which is not allowed for `pat` fragments
   --> src/main.rs:287:47
    |
287 |       

ソースコード

macro_rules! impl_magma {
  ($T:ty, $U:ty, | $op_lhs:pat, $op_rhs:pat | $op_ret:expr) => {
    impl $crate::math::algebra::Magma for $T {
      type Underlying = $U;

      fn op($op_lhs: &Self::Underlying, $op_rhs: &Self::Underlying) -> Self::Underlying {
        $op_ret
      }
    }
  };
}

macro_rules! impl_identity {
  ($T:ty, $id:expr) => {
    impl $crate::math::algebra::Identity for $T {
      fn identity() -> Self::Underlying {
        $id
      }
    }
  };
}

macro_rules! impl_invertible {
  ($T:ty, | $inv_x:pat | $inv_b:expr) => {
    impl $crate::math::algebra::Invertible for $T {
      fn invert($inv_x: &Self::Underlying) -> Self::Underlying {
        $inv_b
      }
    }
  };
}

macro_rules! impl_associative {
  ($T:ty) => {
    impl $crate::math::algebra::Associative for $T {}
  };
}

macro_rules! impl_commutative {
  ($T:ty) => {
    impl $crate::math::algebra::Commutative for $T {}
  };
}

fn solve<R: BufRead, W: Write>(_reader: R, _writer: &mut W) {
  let mut _scanner = Scanner::new(_reader);

  #[allow(unused_macros)]
  macro_rules! scan {
    ($T:ty) => {
      _scanner.next::<$T>().unwrap()
    };
    ($($T:ty),+) => {
      ($(scan!($T)),+)
    };
    ($($T:ty),+; $n:expr $(; $m:expr)*) => {{
      let mut vec = Vec::with_capacity($n);
      for _ in 0..$n {
        vec.push(scan!($($T),+ $(; $m)*));
      }
      vec
    }};
  }

  #[allow(unused_macros)]
  macro_rules! scan_iter {
    ($T:ty; $n:expr) => {
      _scanner.take::<$T>($n).map(|x| x.unwrap())
    };
  }

  #[allow(unused_macros)]
  macro_rules! print {
    ($fmt:expr) => {
      write!(_writer, $fmt).unwrap()
    };
    ($fmt:expr, $($arg:tt)*) => {
      write!(_writer, $fmt, $($arg)*).unwrap()
    };
  }

  #[allow(unused_macros)]
  macro_rules! println {
    ($fmt:expr) => {
      writeln!(_writer, $fmt).unwrap()
    };
    ($fmt:expr, $($arg:tt)*) => {
      writeln!(_writer, $fmt, $($arg)*).unwrap()
    };
  }

  #[allow(unused_macros)]
  macro_rules! eprint {
    ($fmt:expr) => {
      #[cfg(debug_assertions)]
      write!(::std::io::stderr(), $fmt).unwrap()
    };
    ($fmt:expr, $($arg:tt)*) => {
      #[cfg(debug_assertions)]
      write!(::std::io::stderr(), $fmt, $($arg)*).unwrap()
    };
  }

  #[allow(unused_macros)]
  macro_rules! eprintln {
    ($fmt:expr) => {
      #[cfg(debug_assertions)]
      writeln!(::std::io::stderr(), $fmt).unwrap()
    };
    ($fmt:expr, $($arg:tt)*) => {
      #[cfg(debug_assertions)]
      writeln!(::std::io::stderr(), $fmt, $($arg)*).unwrap()
    };
  }

  #[allow(unused_macros)]
  macro_rules! dump {
    ($($x:expr),+) => {
      eprint!("[{}:{}] ", file!(), line!());
      eprintln!(concat!($(stringify!($x), " = {:?}; "),+), $($x),+);
    };
  }

  use data_structures::fenwick_tree::FenwickTree;
  use math::algebra::AdditiveGroup;

  let (n, m) = scan!(usize, usize);
  let mut ab = vec![];
  for _ in 0..n {
    let (a, b) = scan!(usize, usize);
    ab.push(if a < b { (a, b) } else { (b, a) });
  }
  ab.sort();

  let mut seq = FenwickTree::<AdditiveGroup<isize>>::new(m + 1);
  let mut ans = 0;
  for (a, b) in ab {
    ans += (seq.concat(0..a + 1) - seq.concat(0..b + 1)).abs();
    seq.append(a, &1);
    seq.append(b + 1, &-1);
  }
  println!("{}", ans);
}

const CUSTOM_STACK_SIZE_MEBIBYTES: Option<usize> = None;

fn main() {
  if let Some(stack_size_mebibytes) = CUSTOM_STACK_SIZE_MEBIBYTES {
    let builder = thread::Builder::new()
      .name("exec_solver".to_string())
      .stack_size(stack_size_mebibytes * 1024 * 1024);
    builder.spawn(exec_solver).unwrap().join().unwrap();
  } else {
    exec_solver();
  }
}

fn exec_solver() {
  let stdin = stdin();
  let stdout = stdout();
  #[cfg(debug_assertions)]
  let mut writer = stdout.lock();
  #[cfg(not(debug_assertions))]
  let mut writer = ::std::io::BufWriter::new(stdout.lock());
  solve(stdin.lock(), &mut writer);
  writer.flush().unwrap();
}

use io::Scanner;
use std::io::{stdin, stdout, BufRead, Write};
use std::thread;

pub mod math {
  pub mod algebra {
    pub use self::abelian_group::*;
    pub use self::additive_group::*;
    pub use self::associative::*;
    pub use self::commutative::*;
    pub use self::identity::*;
    pub use self::invertible::*;
    pub use self::magma::*;
    pub use self::monoid::*;

    mod magma {
      pub trait Magma {
        type Underlying: Clone;

        fn op(lhs: &Self::Underlying, rhs: &Self::Underlying) -> Self::Underlying;

        fn op_assign(lhs: &mut Self::Underlying, rhs: &Self::Underlying) {
          *lhs = Self::op(lhs, rhs);
        }
      }
    }

    mod identity {
      use math::algebra::Magma;

      pub trait Identity: Magma {
        fn identity() -> Self::Underlying;

        fn prop(a: &Self::Underlying) -> bool
        where
          Self::Underlying: PartialEq,
        {
          Self::op(&Self::identity(), a) == *a && Self::op(a, &Self::identity()) == *a
        }
      }
    }

    mod invertible {
      use math::algebra::{Identity, Magma};

      pub trait Invertible: Magma + Identity {
        fn invert(&Self::Underlying) -> Self::Underlying;

        fn op_inverse(lhs: &Self::Underlying, rhs: &Self::Underlying) -> Self::Underlying {
          Self::op(lhs, &Self::invert(rhs))
        }

        fn op_inverse_assign(lhs: &mut Self::Underlying, rhs: &Self::Underlying) {
          *lhs = Self::op_inverse(lhs, rhs);
        }

        fn prop(a: &Self::Underlying) -> bool
        where
          Self::Underlying: Eq,
        {
          let identity = Self::identity();
          Self::op(a, &Self::invert(a)) == identity && Self::op(&Self::invert(a), a) == identity
        }
      }
    }

    mod associative {
      use math::algebra::Magma;

      pub trait Associative: Magma {
        fn prop(a: &Self::Underlying, b: &Self::Underlying, c: &Self::Underlying) -> bool
        where
          Self::Underlying: Eq,
        {
          Self::op(&Self::op(a, b), c) == Self::op(a, &Self::op(b, c))
        }
      }
    }

    mod commutative {
      use math::algebra::Magma;

      pub trait Commutative: Magma {
        fn prop(a: &Self::Underlying, b: &Self::Underlying) -> bool
        where
          Self::Underlying: Eq,
        {
          Self::op(a, b) == Self::op(b, a)
        }
      }
    }

    #[macro_use]
    mod monoid {
      use math::algebra::{Associative, Identity, Magma};

      pub trait Monoid: Magma + Associative + Identity {}

      impl<T: Magma + Associative + Identity> Monoid for T {}

      macro_rules! impl_monoid {
        ($t:ty, $u:ty, | $op_l:pat, $op_r:pat | $op_b:expr, $id:expr) => {
          impl_magma! { $t, $u, | $op_l, $op_r | $op_b }
          impl_associative! { $t }
          impl_identity! { $t, $id }
        };
      }
    }

    #[macro_use]
    mod abelian_group {
      use math::algebra::{Associative, Commutative, Identity, Invertible, Magma};

      pub trait AbelianGroup: Magma + Associative + Commutative + Identity + Invertible {}

      impl<T: Magma + Associative + Commutative + Identity + Invertible> AbelianGroup for T {}

      macro_rules! impl_abelian_group {
        ($t:ty, $u:ty, | $op_l:pat, $op_r:pat | $op_b:expr, $id:expr, | $inv_x:pat | $inv_b:expr) => {
          impl_magma! { $t, $u, | $op_l, $op_r | $op_b }
          impl_associative! { $t }
          impl_commutative! { $t }
          impl_identity! { $t, $id }
          impl_invertible! { $t, | $inv_x | $inv_b }
        };
      }
    }

    mod additive_group {
      #[allow(unused_imports)]
      use math::algebra::AbelianGroup;
      use std::marker::PhantomData;

      pub struct AdditiveGroup<T> {
        _marker: PhantomData<fn() -> T>,
      }

      macro_rules! impl_additive_group {
        ($($t:ty)+) => {$(
          impl_abelian_group! { AdditiveGroup<$t>, $t, |&lhs, &rhs| lhs + rhs, 0, |&x| -x }
        )+};
      }

      impl_additive_group! { i32 i64 isize }
    }
  }
}

pub mod misc {
  pub use self::byte_char::*;
  pub use self::byte_string::*;

  mod byte_char {
    use std::fmt::{self, Debug, Display, Formatter};

    #[derive(Clone, Copy, PartialOrd, Ord, PartialEq, Eq, Hash)]
    pub struct ByteChar(pub u8);

    impl Debug for ByteChar {
      fn fmt(&self, f: &mut Formatter) -> fmt::Result {
        write!(f, "b\'{}\'", self.0 as char)
      }
    }

    impl Display for ByteChar {
      fn fmt(&self, f: &mut Formatter) -> fmt::Result {
        write!(f, "{}", self.0 as char)
      }
    }
  }

  mod byte_string {
    use misc::ByteChar;
    use std::fmt::{self, Debug, Display, Formatter};

    #[derive(Clone, PartialOrd, Ord, PartialEq, Eq, Hash)]
    pub struct ByteString(pub Vec<ByteChar>);

    impl Debug for ByteString {
      fn fmt(&self, f: &mut Formatter) -> fmt::Result {
        write!(f, "b\"")?;
        for &c in &self.0 {
          write!(f, "{}", c.0 as char)?;
        }
        write!(f, "b\"")
      }
    }

    impl Display for ByteString {
      fn fmt(&self, f: &mut Formatter) -> fmt::Result {
        for &c in &self.0 {
          write!(f, "{}", c)?;
        }
        Ok(())
      }
    }
  }
}

pub mod data_structures {
  pub mod fenwick_tree {
    pub use self::fenwick_tree::FenwickTree;

    pub mod fenwick_tree {
      use math::algebra::{AbelianGroup, Commutative, Monoid};
      use std::iter;
      use std::iter::FromIterator;
      use std::ops::{Range, RangeTo};

      pub struct FenwickTree<M: Monoid + Commutative> {
        vec: Vec<M::Underlying>,
      }

      impl<M: Monoid + Commutative> Clone for FenwickTree<M> {
        fn clone(&self) -> Self {
          FenwickTree { vec: self.vec.clone() }
        }
      }

      impl<M: Monoid + Commutative> FenwickTree<M> {
        pub fn new(len: usize) -> Self {
          FenwickTree {
            vec: vec![M::identity(); len + 1],
          }
        }

        pub fn len(&self) -> usize {
          self.vec.len() - 1
        }

        pub fn append(&mut self, index: usize, x: &M::Underlying) {
          assert!(index < self.len());
          let mut i = index as isize + 1;
          while i <= self.len() as isize {
            M::op_assign(&mut self.vec[i as usize], x);
            i += lsb(i);
          }
        }

        pub fn prefix_concat(&self, index: RangeTo<usize>) -> M::Underlying {
          assert!(index.end <= self.len());
          let mut acc = M::identity();
          let mut r = index.end as isize;
          while r > 0 {
            M::op_assign(&mut acc, &self.vec[r as usize]);
            r -= lsb(r);
          }
          acc
        }
      }

      impl<G: AbelianGroup> FenwickTree<G> {
        pub fn get(&self, index: usize) -> G::Underlying {
          debug_assert!(index < self.len());
          self.concat(index..index + 1)
        }

        pub fn set(&mut self, index: usize, value: &G::Underlying) {
          debug_assert!(index < self.len());
          let diff = G::op_inverse(value, &self.get(index));
          self.append(index, &diff);
        }

        pub fn concat(&self, index: Range<usize>) -> G::Underlying {
          assert!(index.start <= index.end);
          assert!(index.end <= self.len());
          let mut acc = G::identity();
          let mut l = index.start as isize;
          let mut r = index.end as isize;
          while l < r {
            G::op_assign(&mut acc, &self.vec[r as usize]);
            r -= lsb(r);
          }
          while r < l {
            G::op_inverse_assign(&mut acc, &self.vec[l as usize]);
            l -= lsb(l);
          }
          acc
        }
      }

      impl<M: Monoid + Commutative> FromIterator<M::Underlying> for FenwickTree<M> {
        fn from_iter<I: IntoIterator<Item = M::Underlying>>(iter: I) -> Self {
          let mut vec = iter::once(M::identity()).chain(iter).collect::<Vec<_>>();
          vec.shrink_to_fit();
          for i in 1..(vec.len() - 1) as isize {
            let j = (i + lsb(i)) as usize;
            if j < vec.len() {
              vec[j] = M::op(&vec[j], &vec[i as usize]);
            }
          }
          FenwickTree { vec: vec }
        }
      }

      fn lsb(x: isize) -> isize {
        x & !x + 1
      }
    }
  }
}

pub mod io {
  pub use self::from_bytes::FromBytes;
  pub use self::scanner::Scanner;

  mod from_bytes {
    use misc::{ByteChar, ByteString};
    use std::str::{self, FromStr};

    #[derive(Debug)]
    pub struct FromBytesError;

    pub trait FromBytes: Sized {
      type Err;

      fn from_bytes(bytes: &[u8]) -> Result<Self, Self::Err>;
    }

    impl FromBytes for ByteChar {
      type Err = FromBytesError;

      fn from_bytes(bytes: &[u8]) -> Result<Self, Self::Err> {
        if bytes.len() == 1 {
          Ok(ByteChar(*unsafe { bytes.get_unchecked(0) }))
        } else {
          Err(FromBytesError)
        }
      }
    }

    impl FromBytes for ByteString {
      type Err = FromBytesError;

      fn from_bytes(bytes: &[u8]) -> Result<Self, Self::Err> {
        Ok(ByteString(bytes.iter().cloned().map(ByteChar).collect()))
      }
    }

    impl<T: FromStr> FromBytes for T {
      type Err = T::Err;

      fn from_bytes(bytes: &[u8]) -> Result<Self, Self::Err> {
        let s = if cfg!(debug_assertions) {
          str::from_utf8(bytes).unwrap()
        } else {
          unsafe { str::from_utf8_unchecked(bytes) }
        };
        T::from_str(s)
      }
    }
  }

  mod scanner {
    use io::FromBytes;
    use std::io::BufRead;
    use std::marker::PhantomData;

    pub struct Scanner<R> {
      reader: R,
      buffer: Vec<u8>,
      position: usize,
    }

    impl<R: BufRead> Scanner<R> {
      pub fn new(reader: R) -> Self {
        Scanner {
          reader: reader,
          buffer: vec![],
          position: 0,
        }
      }

      pub fn next<T: FromBytes>(&mut self) -> Result<T, T::Err> {
        FromBytes::from_bytes(self.next_bytes().unwrap_or(&[]))
      }

      pub fn take<T: FromBytes>(&mut self, n: usize) -> Take<R, T> {
        Take {
          scanner: self,
          n: n,
          _marker: PhantomData,
        }
      }

      pub fn next_bytes(&mut self) -> Option<&[u8]> {
        if self.buffer.is_empty() {
          self.read_line();
        }
        loop {
          match self.buffer.get(self.position) {
            Some(&b' ') => self.position += 1,
            Some(&b'\n') => self.read_line(),
            Some(_) => break,
            None => return None,
          }
        }
        let start = self.position;
        loop {
          match self.buffer.get(self.position) {
            Some(&b' ') | Some(&b'\n') | None => break,
            Some(_) => self.position += 1,
          }
        }
        Some(&self.buffer[start..self.position])
      }

      fn read_line(&mut self) {
        self.position = 0;
        self.buffer.clear();
        self.reader.read_until(b'\n', &mut self.buffer).unwrap();
      }
    }

    pub struct Take<'a, R: 'a, T> {
      scanner: &'a mut Scanner<R>,
      n: usize,
      _marker: PhantomData<fn() -> T>,
    }

    impl<'a, R: BufRead, T: FromBytes> Iterator for Take<'a, R, T> {
      type Item = Result<T, T::Err>;

      fn next(&mut self) -> Option<Self::Item> {
        if self.n > 0 {
          self.n -= 1;
          Some(self.scanner.next())
        } else {
          None
        }
      }

      fn size_hint(&self) -> (usize, Option<usize>) {
        (self.n, Some(self.n))
      }
    }

    impl<'a, R: BufRead, T: FromBytes> ExactSizeIterator for Take<'a, R, T> {}
  }
}