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

• 問題: No.743 Segments on a Polygon
• ユーザー: くれちー
• 提出日時: 2018-10-05 22:25:24
• 言語: Rust (1.77.0)
• 結果: CE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 11,487 bytes
• コンパイル時間: 4,368 ms
• コンパイル使用メモリ: 85,240 KB
• 最終ジャッジ日時: 2023-08-09 02:40:17
• 合計ジャッジ時間: 5,009 ms
• ジャッジサーバーID （参考情報）: judge11 / judge14

コンパイルメッセージ

error[E0432]: unresolved import `io`
   --> Main.rs:354:9
    |
354 |     use io::FromBytes;
    |         ^^ help: a similar path exists: `crate::io`
    |
    = note: `use` statements changed in Rust 2018; read more at <https://doc.rust-lang.org/edition-guide/rust-2018/module-system/path-clarity.html>

error[E0432]: unresolved import `misc`
   --> Main.rs:275:9
    |
275 |     use misc::ByteChar;
    |         ^^^^ help: a similar path exists: `crate::misc`
    |
    = note: `use` statements changed in Rust 2018; read more at <https://doc.rust-lang.org/edition-guide/rust-2018/module-system/path-clarity.html>

error[E0432]: unresolved import `misc`
   --> Main.rs:307:9
    |
307 |     use misc::{ByteChar, ByteString};
    |         ^^^^ help: a similar path exists: `crate::misc`
    |
    = note: `use` statements changed in Rust 2018; read more at <https://doc.rust-lang.org/edition-guide/rust-2018/module-system/path-clarity.html>

error: aborting due to 3 previous errors

For more information about this error, try `rustc --explain E0432`.

ソースコード

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 foreign_lib::LazySegTree;

  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 = LazySegTree::new(m, |l, r| l + r, 0isize, |x, o| x + o, |l, r| l + r, 0isize);
  let mut ans = 0;
  for (a, b) in ab {
    ans += (seq.query(a, a) - seq.query(b, b)).abs();
    seq.update(a, b, 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;

mod foreign_lib {
  #![allow(unused)]
  // https://github.com/koba-e964/contest/blob/98387e5fc72350e0a96034b17df9fc2beef95123/comm/LazySegTree-poly.rs

  /**
   * Lazy Segment Tree. This data structure is useful for fast folding and updating on intervals of an array
   * whose elements are elements of monoid T. Note that constructing this tree requires the identity
   * element of T and the operation of T. upop must distribute over biop.
   * Reference: http://d.hatena.ne.jp/kyuridenamida/20121114/1352835261
   * Verified by s8pc-2 H (http://s8pc-2.contest.atcoder.jp/submissions/1587536)
   */
  pub struct LazySegTree<T, U, BiOp, UpOp, UpComp> {
    n: usize,
    dat: Vec<T>,
    lazy: Vec<U>,
    e: T,
    biop: BiOp,
    upop: UpOp,
    upcomp: UpComp,
    upe: U, // identity for upop
  }

  impl<T: Clone + Copy, U: Clone + Copy, BiOp: Fn(T, T) -> T, UpOp: Fn(T, U) -> T, UpComp: Fn(U, U) -> U>
    LazySegTree<T, U, BiOp, UpOp, UpComp>
  {
    pub fn new(n_: usize, biop: BiOp, e: T, upop: UpOp, upcomp: UpComp, upe: U) -> Self {
      let mut n = 1;
      while n < n_ {
        n *= 2;
      } // n is a power of 2
      LazySegTree {
        n: n,
        dat: vec![e; 2 * n - 1],
        lazy: vec![upe; 2 * n - 1],
        e: e,
        biop: biop,
        upop: upop,
        upcomp: upcomp,
        upe: upe,
      }
    }
    #[inline]
    fn lazy_evaluate_node(&mut self, k: usize) {
      self.dat[k] = (self.upop)(self.dat[k], self.lazy[k]); // TODO How do biop and upop interact? biop = max, upop = (+) are assumed
      if k < self.n - 1 {
        self.lazy[2 * k + 1] = (self.upcomp)(self.lazy[2 * k + 1], self.lazy[k]);
        self.lazy[2 * k + 2] = (self.upcomp)(self.lazy[2 * k + 2], self.lazy[k]);
      }
      self.lazy[k] = self.upe; // identity for upop
    }
    #[inline]
    fn update_node(&mut self, k: usize) {
      self.dat[k] = (self.biop)(self.dat[2 * k + 1], self.dat[2 * k + 2]);
    }
    fn update_sub(&mut self, a: usize, b: usize, v: U, k: usize, l: usize, r: usize) {
      self.lazy_evaluate_node(k);

      // [a,b) and  [l,r) intersects?
      if r <= a || b <= l {
        return;
      }
      if a <= l && r <= b {
        self.lazy[k] = (self.upcomp)(self.lazy[k], v);
        self.lazy_evaluate_node(k);
        return;
      }

      self.update_sub(a, b, v, 2 * k + 1, l, (l + r) / 2);
      self.update_sub(a, b, v, 2 * k + 2, (l + r) / 2, r);
      self.update_node(k);
    }
    /* ary[i] = upop(ary[i], v) for i in [a, b] (inclusive) */
    #[inline]
    pub fn update(&mut self, a: usize, b: usize, v: U) {
      let n = self.n;
      self.update_sub(a, b + 1, v, 0, 0, n);
    }
    fn update_single_sub(&mut self, a: usize, v: T, k: usize, l: usize, r: usize) {
      self.lazy_evaluate_node(k);

      // [a,b) and  [l,r) intersects?
      if r <= a || a < l {
        return;
      }
      if a == l && r == a + 1 {
        self.dat[k] = v;
        return;
      }

      self.update_single_sub(a, v, 2 * k + 1, l, (l + r) / 2);
      self.update_single_sub(a, v, 2 * k + 2, (l + r) / 2, r);
      self.update_node(k);
    }
    /* ary[i] = upop(ary[i], v) for i in [a, b] (inclusive) */
    #[inline]
    pub fn update_single(&mut self, a: usize, v: T) {
      let n = self.n;
      self.update_single_sub(a, v, 0, 0, n);
    }
    /* l,r are for simplicity */
    fn query_sub(&mut self, a: usize, b: usize, k: usize, l: usize, r: usize) -> T {
      self.lazy_evaluate_node(k);

      // [a,b) and  [l,r) intersect?
      if r <= a || b <= l {
        return self.e;
      }
      if a <= l && r <= b {
        return self.dat[k];
      }
      let vl = self.query_sub(a, b, 2 * k + 1, l, (l + r) / 2);
      let vr = self.query_sub(a, b, 2 * k + 2, (l + r) / 2, r);
      self.update_node(k);
      return (self.biop)(vl, vr);
    }
    /* [a, b] (note: inclusive) */
    #[inline]
    pub fn query(&mut self, a: usize, b: usize) -> T {
      let n = self.n;
      self.query_sub(a, b + 1, 0, 0, n)
    }
  }
}

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 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> {}
  }
}