Maalaus

use std::{convert::Infallible, io::Write, str::FromStr};

#[derive(Clone, Copy, Debug, PartialEq)]
struct Command {
    vertical: bool,
    index: u32,
    color: u32,
}

impl FromStr for Command {
    type Err = Infallible;
    fn from_str(s: &str) -> Result<Self, Self::Err> {
        Ok(match *s.split_ascii_whitespace().collect::<Box<[&str]>>() {
            ["R", row, color] => Command {
                vertical: false,
                index: row.parse::<u32>().unwrap() - 1,
                color: color.parse::<u32>().unwrap() - 1,
            },
            ["C", col, color] => Command {
                vertical: true,
                index: col.parse::<u32>().unwrap() - 1,
                color: color.parse::<u32>().unwrap() - 1,
            },
            _ => panic!(),
        })
    }
}

fn main() {
    let input = std::io::stdin().lines().next().unwrap().unwrap();
    let mut input = input.split_ascii_whitespace().map(|l| l.parse().unwrap());
    let height: u32 = input.next().unwrap();
    let width = input.next().unwrap();
    let colors = input.next().unwrap();
    let instruction_count = input.next().unwrap() as usize;
    drop(input);
    let mut color_counts = [0; 200_000];
    //stores indecies
    let mut last_vert_paints = vec![0u32; width as usize];
    let mut last_hoiz_paints = vec![0u32; height as usize];
    let mut commands: Vec<Option<Command>> = Vec::with_capacity(instruction_count);
    let mut stdout = std::io::stdout().lock();

    for command in std::io::stdin()
        .lines()
        .take(instruction_count)
        .map(|l| l.unwrap().parse::<Command>().unwrap())
    {
        let old_paint_idx = if command.vertical {
            &mut last_vert_paints[command.index as usize]
        } else {
            &mut last_hoiz_paints[command.index as usize]
        };
        let real_old_paint_idx = old_paint_idx.saturating_sub(1);

        let old_crossings =
            inspect_crossings(&commands, real_old_paint_idx, command, &mut color_counts);
        let old_color_amount = if command.vertical {
            color_counts[command.color as usize] += height;
            height - old_crossings
        } else {
            color_counts[command.color as usize] += width;
            width - old_crossings
        };
        if *old_paint_idx != 0 {
            color_counts[commands[real_old_paint_idx as usize]
                .as_ref()
                .unwrap()
                .color as usize] -= old_color_amount;
            commands[real_old_paint_idx as usize] = None;
        }
        commands.push(Some(command));
        *old_paint_idx = commands.len() as u32;
    }
    for color in color_counts.iter().take(colors as usize) {
        print!("{} ", color)
    }
    stdout.flush().unwrap();
}

fn inspect_crossings(
    commands: &[Option<Command>],
    real_old_paint_idx: u32,
    command: Command,
    color_counts: &mut [u32; 200_000],
) -> u32 {
    let commands_to_check = commands
        .iter()
        .rev()
        .take(commands.len() - real_old_paint_idx as usize)
        .flatten();

    commands_to_check
        .filter(|cmd| {
            if cmd.vertical != command.vertical {
                color_counts[cmd.color as usize] -= 1;
                true
            } else {
                false
            }
        })
        .count() as u32
}

Test 1 (public)

Subtask: 1, 3, 4

Verdict: ACCEPTED

Test 2 (public)

Subtask: 3, 4

Verdict: ACCEPTED

Test 3

Subtask: 1, 3, 4

Verdict: ACCEPTED

Test 4

Subtask: 2, 4

Verdict: TIME LIMIT EXCEEDED

Test 5

Subtask: 2, 4

Verdict: TIME LIMIT EXCEEDED

Test 6

Subtask: 3, 4

Verdict: WRONG ANSWER

Test 7

Subtask: 3, 4

Verdict: ACCEPTED

Test 8

Subtask: 4

Verdict: TIME LIMIT EXCEEDED

Test 9

Subtask: 4

Verdict: TIME LIMIT EXCEEDED

Test 10

Subtask: 1, 3, 4

Verdict: ACCEPTED

Test 11

Subtask: 1, 3, 4

Verdict: ACCEPTED

Test 12

Subtask: 2, 4

Verdict: TIME LIMIT EXCEEDED

Test 13

Subtask: 2, 4

Verdict: TIME LIMIT EXCEEDED

Test 14

Subtask: 4

Verdict: TIME LIMIT EXCEEDED

Test 15

Subtask: 4

Verdict: TIME LIMIT EXCEEDED

Test 16

Subtask: 4

Verdict: TIME LIMIT EXCEEDED

Test 17

Subtask: 4

Verdict: TIME LIMIT EXCEEDED