Maalaus

use std::collections::{HashMap, HashSet};
use std::io;

fn read_next<'a, I>(iter: &mut I) -> u32
where
    I: Iterator<Item = &'a str>,
{
    iter.next()
        .expect("invalid input")
        .parse::<u32>()
        .expect("invalid integer")
}

fn main() {
    // Input
    let mut nmkq = String::new();
    io::stdin()
        .read_line(&mut nmkq)
        .expect("failed to read line");
    let mut nmkq = nmkq.split_ascii_whitespace();
    let n = read_next(&mut nmkq);
    let m = read_next(&mut nmkq);
    let k = read_next(&mut nmkq);
    let q = read_next(&mut nmkq);

    let mut row_ops: HashMap<u32, (u32, HashSet<u32>)> = HashMap::new(); // row: (color, lost)
    let mut col_ops: HashMap<u32, (u32, HashSet<u32>)> = HashMap::new();
    let mut sums: Vec<u128> = vec![0; k as usize];

    for _ in 0..q {
        let mut oic = String::new();
        io::stdin()
            .read_line(&mut oic)
            .expect("failed to read line");
        let mut oic = oic.split_ascii_whitespace();
        let o = oic.next().expect("too few arguments");
        let i = read_next(&mut oic) - 1;
        let c = read_next(&mut oic) - 1;
        if k > 1 {
            match o {
                "R" => {
                    let was_painted = row_ops.insert(i, (c, HashSet::new()));
                    match was_painted {
                        Some((color, lost)) => {
                            sums[color as usize] -= (m - lost.into_iter().count() as u32) as u128;
                        }
                        None => {}
                    }
                    for (_, (color, lost)) in col_ops.iter_mut() {
                        if lost.insert(i) {
                            sums[*color as usize] -= 1;
                        }
                    }
                    sums[c as usize] += m as u128;
                }
                "C" => {
                    let was_painted = col_ops.insert(i, (c, HashSet::new()));
                    match was_painted {
                        Some((color, lost)) => {
                            sums[color as usize] -= (n - lost.into_iter().count() as u32) as u128;
                        }
                        None => {}
                    }
                    for (_, (color, lost)) in row_ops.iter_mut() {
                        if lost.insert(i) {
                            sums[*color as usize] -= 1;
                        }
                    }
                    sums[c as usize] += n as u128;
                }
                _ => panic!("illegal operation '{o}'"),
            };
        } else {
            // special case k=1
            match o {
                "R" => {
                    // Loss is impossible
                    if row_ops.insert(i, (0, HashSet::new())).is_none() {
                        sums[0] += (m as usize - col_ops.len()) as u128;
                    }
                }
                "C" => {
                    if col_ops.insert(i, (0, HashSet::new())).is_none() {
                        sums[0] += (n as usize - row_ops.len()) as u128;
                    }
                }
                _ => panic!("illegal operation '{o}'"),
            };
        }
    }

    if k > 1 {
        for value in sums {
            print!("{value} ")
        }
        println!();
    } else {
        println!("{}", sums[0]);
    }
}

Test 1 (public)

Group: 1, 3, 4

Verdict: ACCEPTED

Test 2 (public)

Group: 3, 4

Verdict: ACCEPTED

Test 3

Group: 1, 3, 4

Verdict: ACCEPTED

Test 4

Group: 2, 4

Verdict: ACCEPTED

Test 5

Group: 2, 4

Verdict: ACCEPTED

Test 6

Group: 3, 4

Verdict: ACCEPTED

Test 7

Group: 3, 4

Verdict: ACCEPTED

Test 8

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 1, 3, 4

Verdict: ACCEPTED

Test 11

Group: 1, 3, 4

Verdict: ACCEPTED

Test 12

Group: 2, 4

Verdict: ACCEPTED

Test 13

Group: 2, 4

Verdict: ACCEPTED

Test 14

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 4

Verdict: TIME LIMIT EXCEEDED