fn solve(_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 = 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 { n: usize, dat: Vec, lazy: Vec, e: T, biop: BiOp, upop: UpOp, upcomp: UpComp, upe: U, // identity for upop } impl T, UpOp: Fn(T, U) -> T, UpComp: Fn(U, U) -> U> LazySegTree { 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); 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; } impl FromBytes for ByteChar { type Err = FromBytesError; fn from_bytes(bytes: &[u8]) -> Result { 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 { Ok(ByteString(bytes.iter().cloned().map(ByteChar).collect())) } } impl FromBytes for T { type Err = T::Err; fn from_bytes(bytes: &[u8]) -> Result { 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 { reader: R, buffer: Vec, position: usize, } impl Scanner { pub fn new(reader: R) -> Self { Scanner { reader: reader, buffer: vec![], position: 0, } } pub fn next(&mut self) -> Result { FromBytes::from_bytes(self.next_bytes().unwrap_or(&[])) } pub fn take(&mut self, n: usize) -> Take { 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, n: usize, _marker: PhantomData T>, } impl<'a, R: BufRead, T: FromBytes> Iterator for Take<'a, R, T> { type Item = Result; fn next(&mut self) -> Option { if self.n > 0 { self.n -= 1; Some(self.scanner.next()) } else { None } } fn size_hint(&self) -> (usize, Option) { (self.n, Some(self.n)) } } impl<'a, R: BufRead, T: FromBytes> ExactSizeIterator for Take<'a, R, T> {} } }