AtCoder Beginner Contest 437 D

https://atcoder.jp/contests/abc437/tasks/abc437_d

入力例1で2がらみは、-(2 - 3) + (2 - 1)と考えると、Bで2より大きいものときは負になって、そうでないときは正になります。つまり、自分以下のものの個数を数えればよいです。これは尺取り法を使えば速いですが、二分探索でも十分です。

// Sum of Differences
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}

//////////////////// process ////////////////////

const D: i64 = 998244353;

fn read_input() -> (Vec<i64>, Vec<i64>) {
    let _v: Vec<usize> = read_vec();
    let A: Vec<i64> = read_vec();
    let B: Vec<i64> = read_vec();
    (A, B)
}

// xより小さい項が何個あるか
fn num_less(x: i64, v: &Vec<i64>) -> usize {
    if x <= v[0] {
        return 0
    }
    
    let mut first: usize = 0;
    let mut last: usize = v.len();
    while last - first > 1 {
        let mid = (first + last) / 2;
        if v[mid] >= x {
            last = mid
        }
        else {
            first = mid
        }
    }
    first + 1
}

fn F(mut A: Vec<i64>, mut B: Vec<i64>) -> i64 {
    let N = A.len();
    let M = B.len();
    A.sort();
    B.sort();
    let mut counter: i64 = 0;
    for &a in A.iter() {
        let n = num_less(a+1, &B) as i64;
        counter = (counter + a * (n - (M as i64 - n))) % D
    }
    for &b in B.iter() {
        let n = num_less(b, &A) as i64;
        counter = (counter - b * ((N as i64 - n) - n)) % D
    }
    counter.rem_euclid(D)
}


//////////////////// main ////////////////////

fn main() {
    let (A, B) = read_input();
    println!("{}", F(A, B))
}