Submission #5448466

---

Source Code Expand

#[allow(unused_macros)]
macro_rules! input {
    ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut iter = $ s . split_whitespace ( ) ; let mut next = || { iter . next ( ) . unwrap ( ) } ; input_inner ! { next , $ ( $ r ) * } };
    ( $ ( $ r : tt ) * ) => { let stdin = std :: io :: stdin ( ) ; let mut bytes = std :: io :: Read :: bytes ( std :: io :: BufReader :: new ( stdin . lock ( ) ) ) ; let mut next = move || -> String { bytes . by_ref ( ) . map ( | r | r . unwrap ( ) as char ) . skip_while ( | c | c . is_whitespace ( ) ) . take_while ( | c |! c . is_whitespace ( ) ) . collect ( ) } ; input_inner ! { next , $ ( $ r ) * } };
}
#[allow(unused_macros)]
macro_rules! input_inner {
    ( $ next : expr ) => { };
    ( $ next : expr , ) => { };
    ( $ next : expr , $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let $ var = read_value ! ( $ next , $ t ) ; input_inner ! { $ next $ ( $ r ) * } };
}
#[allow(unused_macros)]
macro_rules! read_value {
    ( $ next : expr , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ next , $ t ) ) ,* ) };
    ( $ next : expr , [ $ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ next , $ t ) ) . collect ::< Vec < _ >> ( ) };
    ( $ next : expr , chars ) => { read_value ! ( $ next , String ) . chars ( ) . collect ::< Vec < char >> ( ) };
    ( $ next : expr , usize1 ) => { read_value ! ( $ next , usize ) - 1 };
    ( $ next : expr , $ t : ty ) => { $ next ( ) . parse ::<$ t > ( ) . expect ( "Parse error" ) };
}

fn main() {
    input! {
        n: usize, m: usize, q: usize,
        trains: [(usize1, usize1); m],
        queries: [(usize1, usize1); q]
    }

    let mut qt = vec![];
    qt.extend(trains.into_iter().map(|(l,r)| (l,r,None)));
    qt.extend(queries.into_iter().enumerate().map(|(i, (l,r))| (l,r,Some(i))));
    qt.sort_by_key(|&(_,r,qi)| (r, qi));

    let mut sq = SqDecomposition::new(n);
    let mut ret = vec![0u64;q];
    for i in 0..qt.len() {
        let (l,r,qi) = qt[i];
        if let Some(src) = qi {
            ret[src] = sq.sum(r+1) - sq.sum(l);
        } else {
            sq.all[l] += 1;
            sq.sq[l/sq.d] += 1;
        }
    }
    for i in 0..q {
        println!("{}", ret[i]);
    }
}

#[derive(Debug)]
#[allow(dead_code)]
struct SqDecomposition {
    all: Vec<u64>,
    sq: Vec<u64>,
    d: usize,
}
#[allow(dead_code)]
impl SqDecomposition {
    fn new(n: usize) -> SqDecomposition {
        let d = (n as f64).sqrt().ceil() as usize;
        SqDecomposition {
            all: vec![0; n],
            sq: vec![0; d],
            d: d,
        }
    }
    #[doc = " [0,n)"]
    fn sum(&self, n: usize) -> u64 {
        let mut ret = 0;
        for i in 0..n / self.d {
            ret += self.sq[i];
        }
        for i in 0..n % self.d {
            ret += self.all[n - n % self.d + i];
        }
        ret
    }
}

Submission Info

Judge Result