#[doc = " https://github.com/hatoo/competitive-rust-snippets"] #[allow(unused_imports)] use std::cmp::{max, min, Ordering}; #[allow(unused_imports)] use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque}; #[allow(unused_imports)] use std::io::{stdin, stdout, BufWriter, Write}; #[allow(unused_imports)] use std::iter::FromIterator; mod util { use std::fmt::Debug; use std::io::{stdin, stdout, BufWriter, StdoutLock}; use std::str::FromStr; #[allow(dead_code)] pub fn line() -> String { let mut line: String = String::new(); stdin().read_line(&mut line).unwrap(); line.trim().to_string() } #[allow(dead_code)] pub fn chars() -> Vec { line().chars().collect() } #[allow(dead_code)] pub fn gets() -> Vec where ::Err: Debug, { let mut line: String = String::new(); stdin().read_line(&mut line).unwrap(); line.split_whitespace() .map(|t| t.parse().unwrap()) .collect() } #[allow(dead_code)] pub fn with_bufwriter) -> ()>(f: F) { let out = stdout(); let writer = BufWriter::new(out.lock()); f(writer) } } #[allow(unused_macros)] macro_rules ! get { ( [ $ t : ty ] ) => { { let mut line : String = String :: new ( ) ; stdin ( ) . read_line ( & mut line ) . unwrap ( ) ; line . split_whitespace ( ) . map ( | t | t . parse ::<$ t > ( ) . unwrap ( ) ) . collect ::< Vec < _ >> ( ) } } ; ( [ $ t : ty ] ; $ n : expr ) => { ( 0 ..$ n ) . map ( | _ | get ! ( [ $ t ] ) ) . collect ::< Vec < _ >> ( ) } ; ( $ t : ty ) => { { let mut line : String = String :: new ( ) ; stdin ( ) . read_line ( & mut line ) . unwrap ( ) ; line . trim ( ) . parse ::<$ t > ( ) . unwrap ( ) } } ; ( $ ( $ t : ty ) ,* ) => { { let mut line : String = String :: new ( ) ; stdin ( ) . read_line ( & mut line ) . unwrap ( ) ; let mut iter = line . split_whitespace ( ) ; ( $ ( iter . next ( ) . unwrap ( ) . parse ::<$ t > ( ) . unwrap ( ) , ) * ) } } ; ( $ t : ty ; $ n : expr ) => { ( 0 ..$ n ) . map ( | _ | get ! ( $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ ( $ t : ty ) ,*; $ n : expr ) => { ( 0 ..$ n ) . map ( | _ | get ! ( $ ( $ t ) ,* ) ) . collect ::< Vec < _ >> ( ) } ; } #[allow(unused_macros)] macro_rules ! debug { ( $ ( $ a : expr ) ,* ) => { eprintln ! ( concat ! ( $ ( stringify ! ( $ a ) , " = {:?}, " ) ,* ) , $ ( $ a ) ,* ) ; } } const BIG_STACK_SIZE: bool = true; #[allow(dead_code)] fn main() { use std::thread; if BIG_STACK_SIZE { thread::Builder::new() .stack_size(32 * 1024 * 1024) .name("solve".into()) .spawn(solve) .unwrap() .join() .unwrap(); } else { solve(); } } #[allow(dead_code)] pub trait Monoid { type T: Clone; fn id() -> Self::T; fn op(a: &Self::T, b: &Self::T) -> Self::T; } #[allow(dead_code)] struct SUM; impl Monoid for SUM { type T = i64; fn id() -> Self::T { 0 } fn op(a: &Self::T, b: &Self::T) -> Self::T { *a + *b } } #[allow(dead_code)] #[doc = " Segment Tree"] pub struct SEG { n: usize, buf: Vec, } impl SEG { #[allow(dead_code)] pub fn new(n: usize) -> SEG { SEG { n: n, buf: vec![M::id().clone(); 2 * n], } } #[allow(dead_code)] pub fn update(&mut self, k: usize, a: M::T) { let mut k = k + self.n; self.buf[k] = a; while k > 0 { k >>= 1; self.buf[k] = M::op(&self.buf[k << 1], &self.buf[(k << 1) | 1]); } } #[allow(dead_code)] pub fn add(&mut self, k: usize, a: &M::T) { let mut k = k + self.n; self.buf[k] = M::op(&self.buf[k], a); while k > 0 { k >>= 1; self.buf[k] = M::op(&self.buf[k << 1], &self.buf[(k << 1) | 1]); } } #[allow(dead_code)] pub fn get(&self, i: usize) -> M::T { self.query(i, i + 1) } #[allow(dead_code)] pub fn query(&self, l: usize, r: usize) -> M::T { let mut vl = M::id(); let mut vr = M::id(); let mut l = l + self.n; let mut r = r + self.n; while l < r { if l & 1 == 1 { vl = M::op(&vl, &self.buf[l]); l += 1; } if r & 1 == 1 { r -= 1; vr = M::op(&self.buf[r], &vr); } l >>= 1; r >>= 1; } M::op(&vl, &vr) } } fn solve() { let (n, m) = get!(usize, usize); let mut ab = get!(usize, usize; n); ab.sort_by_key(|&(a, b)| { let d1 = max(a, b) - min(a, b) - 1; let d2 = m - 2 - d1; min(d1, d2) }); let mut seg: SEG = SEG::new(m); for &(a, b) in &ab { seg.add(a, &1); seg.add(b, &1); } let mut ans = 0; for (a, b) in ab { seg.add(a, &(-1)); seg.add(b, &(-1)); let (a, b) = (min(a, b), max(a, b)); let d1 = max(a, b) - min(a, b) - 1; let d2 = m - 2 - d1; if d1 < d2 { ans += seg.query(a, b); } else { ans += seg.query(b, m); ans += seg.query(0, a); } } println!("{}", ans); }