AtCoder Beginner Contest 351 E

https://atcoder.jp/contests/abc351/tasks/abc351_e

基本的には座標でソートして累積和を取っておけば計算できます。ただ、斜めの座標に変換しておかなければならないです。

// Jump Distance Sum
#![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()
}


//////////////////// Point ////////////////////

type Point = (i64, i64);

fn read_point() -> Point {
    let v = read_vec::<i64>();
    (v[0], v[1])
}


//////////////////// SumDiff ////////////////////

struct SumDiff {
    a: Vec<i64>
}

impl SumDiff {
    fn sum(&self, i: usize) -> i64 {
        (self.a[i+1] - self.a[i]) * (i as i64) - self.a[i]
    }
    
    fn sum_all(&self) -> i64 {
        (0..self.a.len()-1).map(|i| self.sum(i)).sum::<i64>()
    }
    
    fn create(mut xs: Vec<i64>) -> SumDiff {
        xs.sort();
        let L = xs.len();
        let mut a: Vec<i64> = vec![0; L+1];
        for i in 0..L {
            a[i+1] = a[i] + xs[i]
        }
        SumDiff { a }
    }
}


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

fn read_input() -> Vec<Point> {
    let N: usize = read();
    let points: Vec<Point> = (0..N).map(|_| read_point()).collect();
    points
}

fn divide(points: Vec<Point>) -> (Vec<Point>, Vec<Point>) {
    let mut odd_points: Vec<Point> = vec![];
    let mut even_points: Vec<Point> = vec![];
    for &pt in points.iter() {
        if (pt.0 + pt.1) % 2 == 1 {
            odd_points.push(pt)
        }
        else {
            even_points.push(pt)
        }
    }
    (odd_points, even_points)
}

fn create_sumdiffs(points: Vec<Point>) -> (SumDiff, SumDiff) {
    let d = if points.is_empty() { 0 } else { (points[0].0 + points[0].1) % 2 };
    let xs: Vec<i64> = points.iter().map(|&(x, y)| (x+y+d)/2).collect();
    let ys: Vec<i64> = points.iter().map(|&(x, y)| (x-y+d)/2).collect();
    (SumDiff::create(xs), SumDiff::create(ys))
}

fn sum_diff_points(points: Vec<Point>) -> i64 {
    let (sdx, sdy) = create_sumdiffs(points);
    sdx.sum_all() + sdy.sum_all()
}

fn F(points: Vec<Point>) -> i64 {
    let (odd_points, even_points) = divide(points);
    sum_diff_points(odd_points) + sum_diff_points(even_points)
}

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