AtCoder Beginner Contest 395 F

https://atcoder.jp/contests/abc395/tasks/abc395_f

残った歯の高さを定めると簡単に成り立つか成り立たないか分かりやすいので、二分探索します。

// Smooth Occlusion
#![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 ////////////////////

type Range = (i64, i64);

fn read_input() -> (Vec<(i64, i64)>, i64) {
    let v: Vec<usize> = read_vec();
    let (N, X) = (v[0], v[1] as i64);
    let teeth: Vec<(i64, i64)> = (0..N).map(|_| read_vec()).
                                            map(|v| (v[0], v[1])).collect();
    (teeth, X)
}

use std::cmp::{min, max};

fn U_range(pair: (i64, i64), h: i64) -> Range {
    (max(h - pair.1, 0), min(pair.0, h))
}

fn distance(rng1: Range, rng2: Range) -> i64 {
    if rng1.0 < rng2.0 {
        max(rng2.0 - rng1.1, 0)
    }
    else {
        max(rng1.0 - rng2.1, 0)
    }
}

fn intersect(rng1: Range, rng2: Range) -> Range {
    (max(rng1.0, rng2.0), min(rng1.1, rng2.1))
}

fn binary_search(max_H: i64, X: i64, teeth: &Vec<(i64, i64)>) -> i64 {
    let is_valid = |h: i64| -> bool {
        let mut U_rng = U_range(teeth[0], h);
        for &pair in &teeth[1..] {
            let U_rng_cur = U_range(pair, h);
            if distance(U_rng, U_rng_cur) > X {
                return false
            }
            U_rng = intersect((U_rng.0-X, U_rng.1+X), U_rng_cur)
        }
        true
    };
    
    let mut first: i64 = 1;
    let mut last: i64 = max_H + 1;
    while last - first > 1 {
        let mid = (first + last) / 2;
        if is_valid(mid) {
            first = mid
        }
        else {
            last = mid
        }
    }
    first
}

fn F(teeth: Vec<(i64, i64)>, X: i64) -> i64 {
    let N = teeth.len() as i64;
    let max_H = teeth.iter().map(|&(U, D)| U+D).min().unwrap();
    let h = binary_search(max_H, X, &teeth);
    teeth.into_iter().map(|(U, D)| U+D).sum::<i64>() - h * N
}

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