ABC080 D - Recording

問題

atcoder.jp

お気持ち

区間加算して最大値を求める問題
連続する区間は1つにするというところからxorを使いたくなる
チャンネル数が少ないので整数型に収まる
なのでxorでimos法をする

コード

fn main() {
    read_init!(buf);
    let (n, c): (usize, usize) = (read!(buf), read!(buf));
    let stc: Vec<(usize, usize, usize)> = (0..n)
        .map(|_| (read!(buf), read!(buf), read!(buf)))
        .collect();
 
    println!("{}", solve(n, c, stc));
}
 
fn solve(n: usize, c: usize, stc: Vec<(usize, usize, usize)>) -> usize {
    let t_max = stc.iter().map(|(s, t, c)| t).cloned().max().unwrap_or(0);
    let mut imos = Imos::new(t_max + 3);
    for &(s, t, c) in stc.iter() {
        imos.query(s, t + 1, 1 << (c - 1));
    }
    imos.apply()
        .into_iter()
        .map(|x| x.count_ones())
        .max()
        .unwrap_or(0) as usize
}
 
struct Imos {
    array: Vec<u32>,
    len: usize,
}
 
impl Imos {
    fn new(len: usize) -> Self {
        Self {
            array: vec![0; len],
            len: len,
        }
    }
 
    fn query(&mut self, left: usize, right: usize, value: u32) {
        assert!(left < right);
        self.array[left] ^= value;
        self.array[right] ^= value;
    }
 
    fn apply(&self) -> Vec<u32> {
        self.array
            .iter()
            .scan(0u32, |s, &e| {
                *s = *s ^ e;
                Some(*s)
            })
            .collect()
    }
}

atcoder.jp