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) }