AtCoder Beginner Contest 462 D

https://atcoder.jp/contests/abc462/tasks/abc462_d

PriorityQueueに開始時刻の順に入れて、終了時刻-Dを過ぎたら取り出します。その時刻にPriorityQueueにいる人の数でその時刻開始の組合せ数が決まります。

// Accomplice
#![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()
}


//////////////////// Item ////////////////////

#[derive(Debug, Eq, PartialEq, Clone)]
struct Item {
    start: i32,
    end: i32,
}

impl Item {
    fn new(S: i32, T: i32) -> Item {
        Item { start: S, end: T }
    }
    
    fn read() -> Item {
        let v: Vec<i32> = read_vec();
        let (S, T) = (v[0], v[1]);
        Item::new(S, T)
    }
}

impl Ord for Item {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        other.end.cmp(&self.end)
    }
}

impl PartialOrd for Item {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}


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

use std::collections::BinaryHeap;

fn read_input() -> (i32, Vec<Item>) {
    let v: Vec<usize> = read_vec();
    let (N, D) = (v[0], v[1] as i32);
    let candidates = (0..N).map(|_| Item::read()).collect();
    (D, candidates)
}

// 分解の長さのVecにする
fn F(D: i32, mut candidates: Vec<Item>) -> usize {
    candidates.sort_by_key(|c| c.start);
    let max_T = candidates.iter().map(|c| c.end).max().unwrap();
    let mut pq: BinaryHeap<Item> = BinaryHeap::new();
    let mut counter: usize = 0;
    let mut i: usize = 0;
    for t in 1..max_T-D+1 {
        while i < candidates.len() && candidates[i].start == t {
            pq.push(candidates[i].clone());
            i += 1
        }
        while let Some(c) = pq.peek() {
            if c.end - D < t {
                _ = pq.pop()
            }
            else {
                break
            }
        }
        let n = pq.len();
        if n > 0 {
            counter += n * (n - 1) / 2
        }
    }
    counter
}

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