結果
問題 | No.868 ハイパー部分和問題 |
ユーザー | akakimidori |
提出日時 | 2020-03-08 16:05:56 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 3,707 ms / 7,000 ms |
コード長 | 2,241 bytes |
コンパイル時間 | 723 ms |
コンパイル使用メモリ | 164,736 KB |
実行使用メモリ | 9,736 KB |
最終ジャッジ日時 | 2024-04-24 22:40:03 |
合計ジャッジ時間 | 77,677 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 0 ms
5,248 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 0 ms
5,376 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 0 ms
5,376 KB |
testcase_07 | AC | 1 ms
5,376 KB |
testcase_08 | AC | 0 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 | 0 ms
5,376 KB |
testcase_13 | AC | 1 ms
5,376 KB |
testcase_14 | AC | 2,729 ms
9,532 KB |
testcase_15 | AC | 2,700 ms
9,620 KB |
testcase_16 | AC | 2,717 ms
9,580 KB |
testcase_17 | AC | 2,704 ms
9,616 KB |
testcase_18 | AC | 2,653 ms
9,492 KB |
testcase_19 | AC | 3,624 ms
8,144 KB |
testcase_20 | AC | 3,629 ms
8,148 KB |
testcase_21 | AC | 3,625 ms
8,148 KB |
testcase_22 | AC | 3,646 ms
8,272 KB |
testcase_23 | AC | 3,661 ms
8,024 KB |
testcase_24 | AC | 3,707 ms
8,152 KB |
testcase_25 | AC | 3,684 ms
8,156 KB |
testcase_26 | AC | 3,649 ms
8,188 KB |
testcase_27 | AC | 3,590 ms
8,164 KB |
testcase_28 | AC | 3,668 ms
8,036 KB |
testcase_29 | AC | 2,738 ms
9,628 KB |
testcase_30 | AC | 2,629 ms
9,584 KB |
testcase_31 | AC | 2,662 ms
9,628 KB |
testcase_32 | AC | 2,694 ms
9,608 KB |
testcase_33 | AC | 2,721 ms
9,736 KB |
testcase_34 | AC | 3,176 ms
9,644 KB |
testcase_35 | AC | 2,728 ms
9,524 KB |
testcase_36 | AC | 2,944 ms
8,772 KB |
testcase_37 | AC | 2,966 ms
8,772 KB |
testcase_38 | AC | 1 ms
5,376 KB |
testcase_39 | AC | 1 ms
5,376 KB |
ソースコード
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 w = std::mem::size_of::<usize>() * 8; let mut bit = vec![0usize; m / w + 1]; bit[0] = 1; let mut stack = vec![(0, q, edge, bit)]; let out = std::io::stdout(); let mut out = std::io::BufWriter::new(out.lock()); 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 q = v / w; let r = v % w; if r == 0 { for i in (q..bit.len()).rev() { bit[i] |= bit[i - q]; } } else { for i in ((q + 1)..bit.len()).rev() { let x = bit[i - q - 1]; let y = bit[i - q]; bit[i] |= (x >> (w - r)) | (y << r); } bit[q] |= bit[0] << r; } continue; } if l < mid { left.push((x, y, v)); } if mid < r { right.push((x, y, v)); } } if l + 1 == r { writeln!(out, "{}", (bit[m / w] >> (m % w)) & 1).ok(); } else { stack.push((mid, r, right, bit.clone())); stack.push((l, mid, left, bit)); } } } fn main() { run(); }