#441100 (Rust) No.868 ハイパー部分和問題

• 問題: No.868 ハイパー部分和問題
• ユーザー: akakimidori
• 提出日時: 2020-03-08 15:43:05
• 言語: Rust (1.77.0)
• 結果: AC
• 実行時間: 5,373 ms / 7,000 ms
• コード長: 6,512 bytes
• コンパイル時間: 5,058 ms
• コンパイル使用メモリ: 166,656 KB
• 実行使用メモリ: 10,020 KB
• 最終ジャッジ日時: 2024-04-24 22:04:40
• 合計ジャッジ時間: 109,751 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,376 KB
testcase_02	AC	1 ms; 5,376 KB
testcase_03	AC	0 ms; 5,376 KB
testcase_04	AC	1 ms; 5,376 KB
testcase_05	AC	1 ms; 5,376 KB
testcase_06	AC	1 ms; 5,376 KB
testcase_07	AC	1 ms; 5,376 KB
testcase_08	AC	1 ms; 5,376 KB
testcase_09	AC	1 ms; 5,376 KB
testcase_10	AC	1 ms; 5,376 KB
testcase_11	AC	1 ms; 5,376 KB
testcase_12	AC	1 ms; 5,376 KB
testcase_13	AC	1 ms; 5,376 KB
testcase_14	AC	4,261 ms; 10,016 KB
testcase_15	AC	4,304 ms; 9,248 KB
testcase_16	AC	4,031 ms; 10,020 KB
testcase_17	AC	3,916 ms; 9,000 KB
testcase_18	AC	3,105 ms; 9,668 KB
testcase_19	AC	5,146 ms; 8,316 KB
testcase_20	AC	4,987 ms; 8,352 KB
testcase_21	AC	4,993 ms; 8,472 KB
testcase_22	AC	4,754 ms; 8,380 KB
testcase_23	AC	4,730 ms; 8,232 KB
testcase_24	AC	5,373 ms; 8,328 KB
testcase_25	AC	5,236 ms; 8,056 KB
testcase_26	AC	4,868 ms; 8,356 KB
testcase_27	AC	5,093 ms; 8,296 KB
testcase_28	AC	4,580 ms; 8,320 KB
testcase_29	AC	3,843 ms; 9,140 KB
testcase_30	AC	3,818 ms; 9,008 KB
testcase_31	AC	3,869 ms; 9,032 KB
testcase_32	AC	3,131 ms; 9,664 KB
testcase_33	AC	4,274 ms; 8,872 KB
testcase_34	AC	3,889 ms; 9,288 KB
testcase_35	AC	3,937 ms; 9,880 KB
testcase_36	AC	4,333 ms; 8,792 KB
testcase_37	AC	4,346 ms; 8,660 KB
testcase_38	AC	1 ms; 5,376 KB
testcase_39	AC	1 ms; 5,376 KB

ソースコード

// ---------- begin BitSet ----------
#[derive(Clone)]
struct BitSet {
    size: usize,
    a: Vec<usize>,
}

fn bit_size() -> usize {
    8 * std::mem::size_of::<usize>()
}

fn quot_rem(n: usize) -> (usize, usize) {
    let w = bit_size();
    (n / w, n % w)
}

#[allow(dead_code)]
impl BitSet {
    fn new(size: usize) -> Self {
        let w = bit_size();
        BitSet {
            size: size,
            a: vec![0; (size + w - 1) / w],
        }
    }
    fn set_at(&mut self, x: usize) {
        assert!(x < self.size);
        let (q, r) = quot_rem(x);
        self.a[q] |= 1 << r;
    }
    fn clear_at(&mut self, x: usize) {
        assert!(x < self.size);
        let (q, r) = quot_rem(x);
        self.a[q] &= !(1 << r);
    }
    fn get_at(&self, x: usize) -> bool {
        if x >= self.size {
            return false;
        }
        let (q, r) = quot_rem(x);
        (self.a[q] >> r) & 1 == 1
    }
    fn any(&self) -> bool {
        self.a.iter().any(|a| *a != 0)
    }
    fn fix(&mut self) {
        let (q, r) = quot_rem(self.size);
        if r != 0 {
            self.a[q] &= (1 << r) - 1;
        }
    }
    fn clear(&mut self) {
        let len = self.a.len();
        self.a.clear();
        self.a.resize(len, 0);
    }
    fn truncate(&mut self, len: usize) {
        if len >= self.size {
            return;
        }
        let w = bit_size();
        self.a.truncate((len + w - 1) / w);
        self.size = len;
        self.fix();
    }
    fn popcnt(&self) -> usize {
        self.a.iter().fold(0, |s, a| s + a.count_ones() as usize)
    }
    fn shift_left(&self, rhs: usize) -> Self {
        let (q, r) = quot_rem(rhs);
        let mut ans = BitSet::new(self.size + rhs);
        if r == 0 {
            for (x, y) in ans.a[q..].iter_mut().zip(self.a.iter()) {
                *x = *y;
            }
        } else {
            let w = bit_size();
            let mut prev = 0;
            for (x, y) in ans.a[q..].iter_mut().zip(self.a.iter()) {
                *x = (*y << r) | (prev >> (w - r));
                prev = *y;
            }
            *ans.a.last_mut().unwrap() |= prev >> (w - r);
        }
        ans.fix();
        ans
    }
    fn shift_right(&self, rhs: usize) -> Self {
        if rhs >= self.size {
            return BitSet::new(1);
        }
        let (q, r) = quot_rem(rhs);
        let mut ans = BitSet::new(self.size - rhs);
        if r == 0 {
            for (x, y) in ans.a.iter_mut().zip(self.a[q..].iter()) {
                *x = *y;
            }
        } else {
            let w = bit_size();
            let mut prev = 0;
            for (x, y) in ans.a.iter_mut().zip(self.a[q..].iter()).rev() {
                *x |= (*y >> r) | (prev << (w - r));
                prev = *y;
            }
        }
        ans.fix();
        ans
    }
    fn bitwise_or(&self, rhs: &Self) -> Self {
        let (x, y) = if self.size >= rhs.size {(self, rhs)} else {(rhs, self)};
        let mut a = x.a.clone();
        for (a, y) in a.iter_mut().zip(y.a.iter()) {
            *a |= *y;
        }
        BitSet {
            size: x.size,
            a: a,
        }
    }
    fn bitwise_and(&self, rhs: &Self) -> Self {
        let (x, y) = if self.size <= rhs.size {(self, rhs)} else {(rhs, self)};
        let mut a = x.a.clone();
        for (a, y) in a.iter_mut().zip(y.a.iter()) {
            *a &= *y;
        }
        BitSet {
            size: x.size,
            a: a,
        }
    }
    fn bitwise_xor(&self, rhs: &Self) -> Self {
        let (x, y) = if self.size >= rhs.size {(self, rhs)} else {(rhs, self)};
        let mut a = x.a.clone();
        for (a, y) in a.iter_mut().zip(y.a.iter()) {
            *a ^= *y;
        }
        BitSet {
            size: x.size,
            a: a,
        }
    }
    fn bitwise_or_assign(&mut self, rhs: &Self) {
        if self.size < rhs.size {
            self.size = rhs.size;
            self.a.resize(rhs.a.len(), 0);
        }
        for (a, b) in self.a.iter_mut().zip(rhs.a.iter()) {
            *a |= *b;
        }
    }
    fn bitwise_and_assign(&mut self, rhs: &Self) {
        if self.size > rhs.size {
            self.size = rhs.size;
            self.a.resize(rhs.a.len(), 0);
        }
        for (a, b) in self.a.iter_mut().zip(rhs.a.iter()) {
            *a &= *b;
        }
    }
    fn bitwise_xor_assign(&mut self, rhs: &Self) {
        if self.size < rhs.size {
            self.size = rhs.size;
            self.a.resize(rhs.a.len(), 0);
        }
        for (a, b) in self.a.iter_mut().zip(rhs.a.iter()) {
            *a ^= *b;
        }
    }
}
// ---------- end BitSet ----------

use std::io::Read;
use std::io::Write;

fn run() {
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut it = s.trim().split_whitespace();
    let n: usize = it.next().unwrap().parse().unwrap();
    let m: usize = it.next().unwrap().parse().unwrap();
    let mut a = vec![(0usize, 0); n];
    for a in a.iter_mut() {
        a.0 = it.next().unwrap().parse().unwrap();
    }
    let q: usize = it.next().unwrap().parse().unwrap();
    let mut edge = vec![];
    for i in 0..q {
        let x = it.next().unwrap().parse::<usize>().unwrap() - 1;
        let v: usize = it.next().unwrap().parse().unwrap();
        if i > 0 {
            edge.push((a[x].1, i, a[x].0));
        }
        a[x] = (v, i);
    }
    for (a, s) in a {
        edge.push((s, q, a));
    }
    let mut ans = vec![false; q];
    let mut bit = BitSet::new(1);
    bit.set_at(0);
    let mut stack = vec![(0, q, edge, bit)];
    while let Some((l, r, e, mut bit)) = stack.pop() {
        let mid = (l + r) / 2;
        let mut left = vec![];
        let mut right = vec![];
        for (x, y, v) in e {
            if x <= l && r <= y {
                let mut shift = bit.shift_left(v);
                shift.truncate(m + 1);
                bit.bitwise_or_assign(&shift);
                continue;
            }
            if l < mid {
                left.push((x, y, v));
            }
            if mid < r {
                right.push((x, y, v));
            }
        }
        if l + 1 == r {
            ans[l] = bit.get_at(m);
        } else {
            stack.push((l, mid, left, bit.clone()));
            stack.push((mid, r, right, bit));
        }
    }
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    for a in ans {
        writeln!(out, "{}", a as usize).ok();
    }
}

fn main() {
    run();
}