AtCoder Beginner Contest 346 E

https://atcoder.jp/contests/abc346/tasks/abc346_e

逆から考えればよいです。例1なら、下から見て、1 3 2だから、3行目が2になって、2が4個は確定です。次に、1 3 3ですが、3行目はもう終わったので無視です。2 4 0は、4列目を0にしますが、3行目がすでに確定しているので、2個が0になります。2行目が5になって、4列目は確定しているので、5が3個です。最後に1行目と1、2、3列目が残っているので、3個が0になります。

// Paint
#![allow(non_snake_case)]

use std::collections::HashSet;


//////////////////// 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 Paint = (i8, usize, usize);

fn read_paint() -> Paint {
    let v = read_vec();
    let T = v[0] as i8;
    let A = v[1];
    let X = v[2];
    (T, A, X)
}

fn read_input() -> (usize, usize, Vec<Paint>) {
    let v = read_vec();
    let (H, W, M) = (v[0], v[1], v[2]);
    let paints: Vec<Paint> = (0..M).map(|_| read_paint()).collect();
    (H, W, paints)
}

fn F(H: usize, W: usize, paints: Vec<Paint>) {
    let max_X = paints.iter().map(|&(_, _, X)| X).max().unwrap();
    let mut counter: Vec<usize> = vec![0; max_X+1];
    let mut set_H: HashSet<usize> = (1..H+1).collect();
    let mut set_W: HashSet<usize> = (1..W+1).collect();
    for (T, A, X) in paints.into_iter().rev() {
        if T == 1 && set_H.contains(&A) {
            counter[X] += set_W.len();
            set_H.remove(&A);
        }
        else if T == 2 && set_W.contains(&A) {
            counter[X] += set_H.len();
            set_W.remove(&A);
        }
    }
    counter[0] += set_H.len() * set_W.len();
    
    let c: Vec<(usize, usize)> = counter.into_iter().enumerate().
                                        filter(|&(_, n)| n != 0).collect();
    println!("{}", c.len());
    for (x, n) in c.into_iter() {
        println!("{} {}", x, n)
    }
}

fn main() {
    let (H, W, paints) = read_input();
    F(H, W, paints)
}