Submission #3435856

---

Source Code Expand

use std::io::stdin;
use std::str::FromStr;

fn main(){
    let n: usize = get_one();
    let mut xs: Vec<u64> = get_vec();
    let ys: Vec<u64> = get_vec();
    let mut zs: Vec<u64> = get_vec();

    xs.sort();
    zs.sort();

    let mut ans = 0;

    for y in ys.iter() {
        let x_ub = upper_bound(&xs, &|x| x < y);
        let z_lb = lower_bound(&zs, &|z| y < z);
        if let (Some(i), Some(j)) = (x_ub, z_lb) {
            ans += (i+1) as i64 * (n as i64 - j as i64);
        }
    }

    println!("{}", ans);
}

#[allow(dead_code)]
fn get_line() -> String {
    let mut s = String::new();
    match stdin().read_line(&mut s){
        Ok(_) => {s.trim().to_string()}
        Err(_) => String::new()
    }
}

#[allow(dead_code)]
fn get_vec<T: std::str::FromStr>() -> Vec<T> {
    let line = get_line();
    line.split_whitespace().filter_map(|x| x.parse().ok()).collect()
}

#[allow(dead_code)]
fn get_one<T: FromStr + Copy>() -> T {
    let v = get_vec();
    v[0]
}

#[allow(dead_code)]
fn get_pair<T: FromStr + Copy>() -> (T, T) {
    let v = get_vec();
    (v[0], v[1])
}

#[allow(dead_code)]
fn get_triple<T: FromStr + Copy>() -> (T, T, T) {
    let v = get_vec();
    (v[0], v[1], v[2])
}

#[allow(dead_code)]
fn get_chars() -> Vec<char> {
    get_line().chars().collect()
}

fn upper_bound<T, F>(v: &Vec<T>, f: &F) -> Option<usize>
    where F: Fn(&T) -> bool {
    if v.first().map(f) != Some(true) {
        return None;
    }

    let last_idx = (v.len() as i64 -1) as usize;
    if f(&v[last_idx]) {
        return Some(last_idx);
    }

    return Some(upper_bound(v, f, 0, last_idx));

    fn upper_bound<T, F>(v: &Vec<T>, f: &F, left: usize, right: usize) -> usize 
        where F: Fn(&T) -> bool {
        if left+1 == right {
            return left;
        }
        let m = (left + right) / 2;
        if f(&v[m]) {
            return upper_bound(v, f, m, right);
        } else {
            return upper_bound(v, f, left, m);
        }
    }
}

fn lower_bound<T, F>(v: &Vec<T>, f: &F) -> Option<usize>
    where F: Fn(&T) -> bool {
    if v.last().map(f) != Some(true) {
        return None;
    }

    if let Some(i) = upper_bound(v, &|x| !f(x)) {
        return Some(i + 1);
    } else {
        return Some(0);
    }
}

Submission Info

Judge Result