// -*- coding:utf-8-unix -*- // #![feature(map_first_last)] #![allow(dead_code)] #![allow(unused_imports)] #![allow(unused_macros)] use std::collections::*; use std::convert::*; use std::convert::{From, Into}; use std::fmt::Debug; use std::fs::File; use std::io::prelude::*; use std::io::*; use std::marker::Copy; use std::mem::*; use std::ops::Bound::*; use std::ops::{Add, Mul, Neg, Sub}; use std::str; use std::vec; use std::{cmp, process::Output}; use std::{cmp::Ordering, env::consts::DLL_PREFIX}; use std::{cmp::Ordering::*, f32::consts::PI}; const INF: i64 = 1223372036854775807; const UINF: usize = INF as usize; const FINF: f64 = 122337203685.0; const INF128: i128 = 1223372036854775807000000000000; const LINF: i64 = 2147483647; const MOD: i64 = 1000000007; const T: bool = true; const F: bool = false; const MPI: f64 = 3.14159265358979323846264338327950288f64; // const MOD: i64 = 998244353; // const MOD: i64 = INF; const UMOD: usize = MOD as usize; use std::cmp::*; use std::collections::*; use std::io::stdin; use std::io::stdout; use std::io::Write; macro_rules! p { ($x:expr) => { println!("{}", $x); }; } macro_rules! d { ($x:expr) => { println!("{:?}", $x); }; } macro_rules! dd { (x:expr) => { dbg!(x); }; } macro_rules! chmin { ($base:expr, $($cmps:expr),+ $(,)*) => {{ let cmp_min = min!($($cmps),+); if $base > cmp_min { $base = cmp_min; true } else { false } }}; } macro_rules! chmax { ($base:expr, $($cmps:expr),+ $(,)*) => {{ let cmp_max = max!($($cmps),+); if $base < cmp_max { $base = cmp_max; true } else { false } }}; } macro_rules! min { ($a:expr $(,)*) => {{ $a }}; ($a:expr, $b:expr $(,)*) => {{ std::cmp::min($a, $b) }}; ($a:expr, $($rest:expr),+ $(,)*) => {{ std::cmp::min($a, min!($($rest),+)) }}; } macro_rules! max { ($a:expr $(,)*) => {{ $a }}; ($a:expr, $b:expr $(,)*) => {{ std::cmp::max($a, $b) }}; ($a:expr, $($rest:expr),+ $(,)*) => {{ std::cmp::max($a, max!($($rest),+)) }}; } // use str::Chars; // use str::Chars; #[allow(dead_code)] fn read() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } #[allow(dead_code)] fn readi() -> (i64) { let mut str = String::new(); let _ = stdin().read_line(&mut str).unwrap(); let mut iter = str.split_whitespace(); iter.next().unwrap().parse::().unwrap() } #[allow(dead_code)] fn read_vec() -> Vec { read::() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect() } #[allow(dead_code)] fn read_vec2(n: u32) -> Vec> { (0..n).map(|_| read_vec()).collect() } #[allow(dead_code)] fn readii() -> (i64, i64) { let mut str = String::new(); let _ = stdin().read_line(&mut str).unwrap(); let mut iter = str.split_whitespace(); ( iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), ) } fn readff() -> (f64, f64) { let mut str = String::new(); let _ = stdin().read_line(&mut str).unwrap(); let mut iter = str.split_whitespace(); ( iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), ) } #[allow(dead_code)] fn readiii() -> (i64, i64, i64) { let mut str = String::new(); let _ = stdin().read_line(&mut str).unwrap(); let mut iter = str.split_whitespace(); ( iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), ) } #[allow(dead_code)] fn readuu() -> (usize, usize) { let mut str = String::new(); let _ = stdin().read_line(&mut str).unwrap(); let mut iter = str.split_whitespace(); ( iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), ) } fn readcc() -> (char, char) { let mut str = String::new(); let _ = stdin().read_line(&mut str).unwrap(); let mut iter = str.split_whitespace(); ( iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), ) } #[allow(dead_code)] fn readuuu() -> (usize, usize, usize) { let mut str = String::new(); let _ = stdin().read_line(&mut str).unwrap(); let mut iter = str.split_whitespace(); ( iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), ) } #[allow(dead_code)] fn readuuuu() -> (usize, usize, usize, usize) { let mut str = String::new(); let _ = stdin().read_line(&mut str).unwrap(); let mut iter = str.split_whitespace(); ( iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), ) } fn readiiii() -> (i64, i64, i64, i64) { let mut str = String::new(); let _ = stdin().read_line(&mut str).unwrap(); let mut iter = str.split_whitespace(); ( iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), ) } mod complex { #[derive(Clone, Copy, Debug)] pub struct Complex { pub x: f64, pub y: f64, } impl Complex { pub fn new(x: f64, y: f64) -> Self { Complex { x: x, y: y } } pub fn polar(r: f64, theta: f64) -> Self { Complex::new(r * theta.cos(), r * theta.sin()) } pub fn conj(&self) -> Self { Complex::new(self.x, -self.y) } pub fn abs(&self) -> f64 { (self.x * self.x + self.y * self.y).sqrt() } pub fn arg(&self) -> f64 { self.y.atan2(self.x) } } use std::ops::*; impl Add for Complex { type Output = Self; fn add(self, rhs: Self) -> Self { Complex::new(self.x + rhs.x, self.y + rhs.y) } } impl Sub for Complex { type Output = Self; fn sub(self, rhs: Self) -> Self { Complex::new(self.x - rhs.x, self.y - rhs.y) } } impl Mul for Complex { type Output = Self; fn mul(self, rhs: Self) -> Self { Complex::new( self.x * rhs.x - self.y * rhs.y, self.x * rhs.y + self.y * rhs.x, ) } } impl Div for Complex { type Output = Self; fn div(self, rhs: Self) -> Self { let z = self * rhs.conj(); let a = rhs.x * rhs.x + rhs.y * rhs.y; Complex::new(z.x / a, z.y / a) } } impl AddAssign for Complex { fn add_assign(&mut self, rhs: Self) { *self = *self + rhs } } impl SubAssign for Complex { fn sub_assign(&mut self, rhs: Self) { *self = *self - rhs } } impl MulAssign for Complex { fn mul_assign(&mut self, rhs: Self) { *self = *self * rhs } } impl DivAssign for Complex { fn div_assign(&mut self, rhs: Self) { *self = *self / rhs } } } pub type Complex = complex::Complex; pub fn multiply(a: &[i64], b: &[i64], mo: i64) -> Vec { let n = a.len(); let m = b.len(); let mut fa = vec![]; let mut fb = vec![]; for i in 0..n { fa.push(a[i] as f64) } for i in 0..m { fb.push(b[i] as f64) } let fc = convolve(fa, fb); let mut c = vec![]; for x in fc { let v = (x + 0.5) as i64; c.push(v % mo); } c } #[doc = "convolve two waves a[x],b[y] to c[x+y]. O(nlogn)"] pub fn convolve(a: Vec, b: Vec) -> Vec { let n = a.len() + b.len() - 1; let mut m = 1; while m < n { m *= 2; } let mut x = vec![Complex::new(0., 0.); m]; for i in 0..a.len() { x[i] = Complex::new(a[i], 0.); } let mut y = vec![Complex::new(0., 0.); m]; for i in 0..b.len() { y[i] = Complex::new(b[i], 0.); } let X = fast_fourier_transform(x, false); let Y = fast_fourier_transform(y, false); let mut Z = vec![Complex::new(0., 0.); m]; for i in 0..m { Z[i] = X[i] * Y[i]; } let z = fast_fourier_transform(Z, true); let mut ret = vec![0.; m]; for i in 0..m { ret[i] = z[i].x; } ret } pub fn fast_fourier_transform(arr: Vec, inv: bool) -> Vec { let n = arr.len(); assert!(n.count_ones() == 1, "the length of array is not square"); let mut a: Vec<_> = arr.to_vec(); let mut tmp: Vec<_> = (0..n).map(|_| Complex::new(0., 0.)).collect(); let mut ai: Vec<_> = (0..n).map(|i| i).collect(); let mut ti: Vec<_> = (0..n).map(|_| 0).collect(); let bit = n.trailing_zeros(); let f = if inv { -1.0 } else { 1.0 }; for si in (0..bit).rev() { let s = 1 << si; std::mem::swap(&mut a, &mut tmp); std::mem::swap(&mut ai, &mut ti); let zeta = Complex::polar(1.0, std::f64::consts::PI * 2.0 * f / (s << 1) as f64); let mut z_i = Complex::new(1.0, 0.0); let mut ev = 0; let mut od = 1; for i in 0..n { if (i & s) != 0 { a[i] = (tmp[i - s] - tmp[i]) * z_i; ai[i] = ti[od]; od += 2; z_i *= zeta; } else { a[i] = tmp[i] + tmp[i + s]; ai[i] = ti[ev]; ev += 2; z_i = Complex::new(1.0, 0.0); } } } std::mem::swap(&mut a, &mut tmp); let inv_n = if inv { n as f64 } else { 1.0 }; for i in 0..n { a[ai[i]] = Complex::new(tmp[i].x / inv_n, tmp[i].y / inv_n); } a } /// Equivalent to std::lowerbound and std::upperbound in c++ pub trait BinarySearch { fn lower_bound(&self, x: &T) -> usize; fn upper_bound(&self, x: &T) -> usize; } impl BinarySearch for [T] { fn lower_bound(&self, x: &T) -> usize { let mut low = 0; let mut high = self.len(); while low != high { let mid = (low + high) / 2; match self[mid].cmp(x) { Ordering::Less => { low = mid + 1; } Ordering::Equal | Ordering::Greater => { high = mid; } } } low } fn upper_bound(&self, x: &T) -> usize { let mut low = 0; let mut high = self.len(); while low != high { let mid = (low + high) / 2; match self[mid].cmp(x) { Ordering::Less | Ordering::Equal => { low = mid + 1; } Ordering::Greater => { high = mid; } } } low } } fn solve() { let n: usize = read(); let mut a: Vec = read_vec(); let mut b: Vec = read_vec(); let mut c: Vec = read_vec(); let mut vb = vec![0; 3030]; let mut vc = vec![0; 3030]; for i in 0..n { vb[b[i]] += 1; vc[c[i]] += 1; } let mut vf = multiply(&vb, &vc, MOD); for i in 1..vf.len() { vf[i] += vf[i - 1]; } a.sort(); b.sort(); c.sort(); let mut res = 0; for i in 0..n { let p1 = b.upper_bound(&a[i]); let p2 = c.upper_bound(&a[i]); res += p1 * p2; res -= vf[a[i]] as usize; } p!(res); return; } fn main() { solve(); }