結果
問題 | No.885 アマリクエリ |
ユーザー | akakimidori |
提出日時 | 2020-09-14 08:39:32 |
言語 | Rust (1.77.0 + proconio) |
結果 |
AC
|
実行時間 | 57 ms / 2,000 ms |
コード長 | 4,448 bytes |
コンパイル時間 | 13,609 ms |
コンパイル使用メモリ | 403,720 KB |
実行使用メモリ | 12,216 KB |
最終ジャッジ日時 | 2024-06-22 00:36:19 |
合計ジャッジ時間 | 16,325 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 41 ms
11,248 KB |
testcase_01 | AC | 40 ms
12,024 KB |
testcase_02 | AC | 57 ms
12,188 KB |
testcase_03 | AC | 25 ms
12,172 KB |
testcase_04 | AC | 25 ms
12,216 KB |
testcase_05 | AC | 21 ms
11,504 KB |
testcase_06 | AC | 17 ms
10,616 KB |
testcase_07 | AC | 8 ms
11,148 KB |
testcase_08 | AC | 12 ms
6,944 KB |
testcase_09 | AC | 43 ms
12,104 KB |
testcase_10 | AC | 1 ms
6,944 KB |
testcase_11 | AC | 0 ms
6,940 KB |
testcase_12 | AC | 1 ms
6,940 KB |
testcase_13 | AC | 1 ms
6,940 KB |
testcase_14 | AC | 1 ms
6,940 KB |
testcase_15 | AC | 1 ms
6,944 KB |
testcase_16 | AC | 1 ms
6,940 KB |
testcase_17 | AC | 1 ms
6,940 KB |
testcase_18 | AC | 2 ms
6,940 KB |
testcase_19 | AC | 1 ms
6,940 KB |
testcase_20 | AC | 1 ms
6,940 KB |
testcase_21 | AC | 1 ms
6,944 KB |
コンパイルメッセージ
warning: function `update_set` is never used --> src/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
ソースコード
// ---------- 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(); } }