AtCoder Beginner Contest 355 D

https://atcoder.jp/contests/abc355/tasks/abc355_d

区間の両端の点を一つのVecに入れて位置でソートします。その際、左右と何番目の区間かの情報も入れておきます。そして、位置の左から見ていって、左だったら何番目の左かを記録して、右だったらその区間内で左が何回通過したかを足していきます。

// Intersecting Intervals
#![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 Interval = (u64, u64);

fn read_interval() -> Interval {
    let v: Vec<u64> = read_vec();
    let (l, r) = (v[0], v[1]);
    (l, r)
}

fn read_input() -> Vec<Interval> {
    let N: usize = read();
    let intervals: Vec<Interval> = (0..N).map(|_| read_interval()).collect();
    intervals
}

fn sort_points(intervals: Vec<Interval>) -> Vec<(u64, char, usize)> {
    let mut v: Vec<(u64, char, usize)> = vec![];
    for (i, (l, r)) in intervals.into_iter().enumerate() {
        v.push((l, 'l', i));
        v.push((r, 'r', i))
    }
    v.sort();
    v
}

fn F(intervals: Vec<Interval>) -> u64 {
    let N = intervals.len();
    let points = sort_points(intervals);
    let mut lefts: Vec<u64> = vec![0; N];
    let mut s: u64 = 0;
    let mut counter_left: u64 = 0;
    for (_, side, i) in points.into_iter() {
        if side == 'l' {    // left
            lefts[i] = counter_left;
            counter_left += 1
        }
        else {
            s += counter_left - lefts[i] - 1
        }
    }
    s
}

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