AtCoder Beginner Contest 391 D

https://atcoder.jp/contests/abc391/tasks/abc391_d

同じXで集めてYが小さいほうから積みます。そうしたときに、下から同じ層のブロックが全て揃っていなければその層のブロックは消えることはありません。全て揃っているとき、消える時間は最大の高さと同じです。

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

fn YesNo(b: bool) -> String {
    return if b { "Yes" } else { "No" }.to_string()
}


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

type Block = (usize, usize);

fn read_block() -> Block {
    let v: Vec<usize> = read_vec();
    let (X, Y) = (v[0] - 1, v[1] - 1);
    (X, Y)
}

type Query = (i32, usize);

fn read_query() -> Query {
    let v: Vec<usize> = read_vec();
    let (T, A) = (v[0] as i32, v[1] - 1);
    (T, A)
}

fn read_input() -> (usize, Vec<Block>, usize) {
    let v: Vec<usize> = read_vec();
    let (N, W) = (v[0], v[1]);
    let blocks: Vec<Block> = (0..N).map(|_| read_block()).collect();
    let Q: usize = read();
    (W, blocks, Q)
}

fn sort_blocks(blocks: Vec<Block>, W: usize) -> Vec<Vec<(usize, usize)>> {
    let mut b: Vec<(usize, Block)> = blocks.into_iter().enumerate().collect();
    b.sort_by_key(|&(_, bl)| { bl });
    let mut blks: Vec<Vec<(usize, usize)>> = vec![vec![]; W];
    for (i, (X, Y)) in b.into_iter() {
        blks[X].push((i, Y))
    }
    blks
}

fn find_max_Y(i: usize, blks: &Vec<Vec<(usize, usize)>>) -> usize {
    let mut max_y = 0;
    for x in 0..blks.len() {
        if blks[x].len() <= i {
            return usize::MAX
        }
        else if blks[x][i].1 > max_y {
            max_y = blks[x][i].1
        }
    }
    max_y
}

fn find_vanishing_time(blks: Vec<Vec<(usize, usize)>>, N: usize) -> Vec<i32> {
    let W = blks.len();
    let mut vanishing: Vec<i32> = vec![i32::MAX; N];
    for i in 0.. {
        let max_y = find_max_Y(i, &blks);
        if max_y == usize::MAX {
            break
        }
        for x in 0..W {
            vanishing[blks[x][i].0] = max_y as i32
        }
    }
    vanishing
}

fn F(W: usize, blocks: Vec<Block>, Q: usize) {
    let N = blocks.len();
    let blks = sort_blocks(blocks, W);
    let vanishing = find_vanishing_time(blks, N);
    
    for _ in 0..Q {
        let (T, A) = read_query();
        println!("{}", YesNo(T <= vanishing[A]))
    }
}

fn main() {
    let (W, blocks, Q) = read_input();
    F(W, blocks, Q)
}