結果
問題 | No.885 アマリクエリ |
ユーザー | akakimidori |
提出日時 | 2020-09-14 08:39:32 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 65 ms / 2,000 ms |
コード長 | 4,448 bytes |
コンパイル時間 | 6,850 ms |
コンパイル使用メモリ | 152,820 KB |
実行使用メモリ | 14,260 KB |
最終ジャッジ日時 | 2023-09-04 00:31:57 |
合計ジャッジ時間 | 8,987 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 29 ms
12,164 KB |
testcase_01 | AC | 51 ms
12,176 KB |
testcase_02 | AC | 65 ms
12,172 KB |
testcase_03 | AC | 34 ms
14,260 KB |
testcase_04 | AC | 34 ms
14,164 KB |
testcase_05 | AC | 29 ms
12,164 KB |
testcase_06 | AC | 24 ms
10,612 KB |
testcase_07 | AC | 10 ms
11,116 KB |
testcase_08 | AC | 14 ms
4,380 KB |
testcase_09 | AC | 56 ms
12,160 KB |
testcase_10 | AC | 1 ms
4,376 KB |
testcase_11 | AC | 0 ms
4,380 KB |
testcase_12 | AC | 1 ms
4,380 KB |
testcase_13 | AC | 1 ms
4,376 KB |
testcase_14 | AC | 1 ms
4,376 KB |
testcase_15 | AC | 1 ms
4,376 KB |
testcase_16 | AC | 1 ms
4,380 KB |
testcase_17 | AC | 1 ms
4,376 KB |
testcase_18 | AC | 1 ms
4,376 KB |
testcase_19 | AC | 1 ms
4,376 KB |
testcase_20 | AC | 1 ms
4,376 KB |
testcase_21 | AC | 1 ms
4,376 KB |
コンパイルメッセージ
warning: function `update_set` is never used --> Main.rs:98:4 | 98 | fn update_set(k: usize, l: usize, r: usize, x: usize, y: usize, v: i64, node: &mut [Node]) { | ^^^^^^^^^^ | = note: `#[warn(dead_code)]` on by default warning: 1 warning emitted
ソースコード
// ---------- begin scannner ---------- #[allow(dead_code)] mod scanner { use std; use std::io::Read; use std::str::FromStr; use std::str::SplitWhitespace; pub struct Scanner<'a> { it: SplitWhitespace<'a>, } impl<'a> Scanner<'a> { pub fn new(s: &'a String) -> Scanner<'a> { Scanner { it: s.split_whitespace(), } } pub fn next<T: FromStr>(&mut self) -> T { match self.it.next().unwrap().parse::<T>() { Ok(v) => v, _ => panic!("Scanner error"), } } pub fn next_chars(&mut self) -> Vec<char> { self.next::<String>().chars().collect() } pub fn next_vec<T: FromStr>(&mut self, len: usize) -> Vec<T> { (0..len).map(|_| self.next()).collect() } } pub fn read_string() -> String { let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s } } // ---------- end scannner ---------- use std::cmp::*; use std::io::Write; fn main() { let sc = scanner::read_string(); let mut sc = scanner::Scanner::new(&sc); let out = std::io::stdout(); let mut out = std::io::BufWriter::new(out.lock()); run(&mut sc, &mut out); } struct Node { max: i64, only: bool, sum: i64, len: i64, } impl Node { fn fold(&self, rhs: &Self) -> Self { let sum = self.sum + rhs.sum; let len = self.len + rhs.len; let (max, only) = match self.max.cmp(&rhs.max) { Ordering::Equal => (self.max, self.only && rhs.only), Ordering::Greater => (self.max, false), Ordering::Less => (rhs.max, false), }; Node { max, only, sum, len, } } fn update_set(&mut self, v: i64) { self.sum = v * self.len; self.max = v; self.only = true; } fn break_mod(&self, v: i64) -> bool { self.max < v } fn tag_mod(&self, v: i64) -> bool { self.max >= v && self.only } fn update_mod(&mut self, v: i64) { assert!(self.tag_mod(v)); let x = self.max % v; self.update_set(x); } } fn propagate(k: usize, node: &mut [Node]) { assert!(2 * k + 1 < node.len()); if node[k].only { node[2 * k].update_set(node[k].max); node[2 * k + 1].update_set(node[k].max); } } fn update_set(k: usize, l: usize, r: usize, x: usize, y: usize, v: i64, node: &mut [Node]) { if y <= l || r <= x { return; } if x <= l && r <= y { node[k].update_set(v); return; } propagate(k, node); let m = (l + r) / 2; update_set(2 * k, l, m, x, y, v, node); update_set(2 * k + 1, m, r, x, y, v, node); node[k] = node[2 * k].fold(&node[2 * k + 1]); } fn update_mod(k: usize, l: usize, r: usize, x: usize, y: usize, v: i64, node: &mut [Node]) { if y <= l || r <= x || node[k].break_mod(v) { return; } if x <= l && r <= y && node[k].tag_mod(v) { node[k].update_mod(v); return; } propagate(k, node); let m = (l + r) / 2; update_mod(2 * k, l, m, x, y, v, node); update_mod(2 * k + 1, m, r, x, y, v, node); node[k] = node[2 * k].fold(&node[2 * k + 1]); } fn find_sum(k: usize, l: usize, r: usize, x: usize, y: usize, node: &mut [Node]) -> i64 { if y <= l || r <= x { return 0; } if x <= l && r <= y { return node[k].sum; } propagate(k, node); let m = (l + r) / 2; find_sum(2 * k, l, m, x, y, node) + find_sum(2 * k + 1, m, r, x, y, node) } fn run(sc: &mut scanner::Scanner, out: &mut std::io::BufWriter<std::io::StdoutLock>) { let n: usize = sc.next(); let size = n.next_power_of_two(); let mut node = (0..(2 * size)) .map(|_| Node { max: 0, only: true, sum: 0, len: 1, }) .collect::<Vec<_>>(); for node in node[size..].iter_mut().take(n) { node.len = 1; node.update_set(sc.next()); } for i in (1..size).rev() { node[i] = node[2 * i].fold(&node[2 * i + 1]); } let m: usize = sc.next(); for _ in 0..m { let x: i64 = sc.next(); update_mod(1, 0, size, 0, n, x, &mut node); let ans = find_sum(1, 0, size, 0, n, &mut node); writeln!(out, "{}", ans).ok(); } }