AtCoder Beginner Contest 377 D

https://atcoder.jp/contests/abc377/tasks/abc377_d

例3だと、[5, 19]は[8, 12]を含みますが、この場合[5, 19]は要らないないです。こういう区間を消すと楽になります。

// Many Segments 2
#![allow(non_snake_case)]

use std::collections::BTreeSet;


//////////////////// 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() -> (i64, Vec<Range>) {
    let v: Vec<usize> = read_vec();
    let (N, M) = (v[0], v[1] as i64);
    let LRs: Vec<Range> = (0..N).map(|_| read_vec::<i64>()).
                                    map(|w| (w[0], w[1])).collect();
    (M, LRs)
}

fn T(n: i64) -> i64 {
    n * (n + 1) / 2
}

fn compress_LRs(mut LRs: Vec<Range>) -> Vec<Range> {
    LRs.sort();
    let mut set_RLs: BTreeSet<Range> = BTreeSet::new();
    for (L, R) in LRs.into_iter() {
        while let Some(&(R1, _)) = set_RLs.last() {
            if R1 < R {
                break
            }
            set_RLs.pop_last();
        }
        set_RLs.insert((R, L));
    }
    set_RLs.into_iter().map(|(R, L)| (L, R)).collect::<Vec<Range>>()
}

fn F(M: i64, mut LRs: Vec<Range>) -> i64 {
    LRs = compress_LRs(LRs);
    let (L0, R0) = LRs[0];
    let mut counter = T(R0 - 1) - T(R0 - L0);
    for (i, &(L, R)) in LRs.iter().enumerate() {
        let (L1, R1) = if i == LRs.len() - 1 { (M+1, M+1) } else { LRs[i+1] };
        counter += R - L;
        counter += T(R1 - L - 1) - T(R1 - L1);
    }
    counter
}

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