結果
問題 | No.1099 Range Square Sum |
ユーザー | koba-e964 |
提出日時 | 2020-06-26 21:51:20 |
言語 | Rust (1.77.0 + proconio) |
結果 |
WA
|
実行時間 | - |
コード長 | 7,709 bytes |
コンパイル時間 | 11,993 ms |
コンパイル使用メモリ | 378,020 KB |
実行使用メモリ | 19,072 KB |
最終ジャッジ日時 | 2024-07-04 20:42:15 |
合計ジャッジ時間 | 16,031 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 1 ms
5,376 KB |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | AC | 1 ms
5,376 KB |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | WA | - |
コンパイルメッセージ
warning: unused macro definition: `input` --> src/main.rs:7:14 | 7 | macro_rules! input { | ^^^^^ | = note: `#[warn(unused_macros)]` on by default warning: unused macro definition: `input_inner` --> src/main.rs:23:14 | 23 | macro_rules! input_inner { | ^^^^^^^^^^^ warning: unused macro definition: `read_value` --> src/main.rs:32:14 | 32 | macro_rules! read_value { | ^^^^^^^^^^
ソースコード
#[allow(unused_imports)] use std::cmp::*; #[allow(unused_imports)] use std::collections::*; use std::io::{Read, Write, BufWriter}; // https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 macro_rules! input { ($($r:tt)*) => { let stdin = std::io::stdin(); let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock())); let mut next = move || -> String{ bytes .by_ref() .map(|r|r.unwrap() as char) .skip_while(|c|c.is_whitespace()) .take_while(|c|!c.is_whitespace()) .collect() }; input_inner!{next, $($r)*} }; } macro_rules! input_inner { ($next:expr) => {}; ($next:expr, ) => {}; ($next:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($next, $t); input_inner!{$next $($r)*} }; } macro_rules! read_value { ($next:expr, [graph1; $len:expr]) => {{ let mut g = vec![vec![]; $len]; let ab = read_value!($next, [(usize1, usize1)]); for (a, b) in ab { g[a].push(b); g[b].push(a); } g }}; ($next:expr, ( $($t:tt),* )) => { ( $(read_value!($next, $t)),* ) }; ($next:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>() }; ($next:expr, chars) => { read_value!($next, String).chars().collect::<Vec<char>>() }; ($next:expr, usize1) => (read_value!($next, usize) - 1); ($next:expr, [ $t:tt ]) => {{ let len = read_value!($next, usize); read_value!($next, [$t; len]) }}; ($next:expr, $t:ty) => ($next().parse::<$t>().expect("Parse error")); } #[allow(unused)] macro_rules! debug { ($($format:tt)*) => (write!(std::io::stderr(), $($format)*).unwrap()); } #[allow(unused)] macro_rules! debugln { ($($format:tt)*) => (writeln!(std::io::stderr(), $($format)*).unwrap()); } fn get_word() -> String { let stdin = std::io::stdin(); let mut stdin=stdin.lock(); let mut u8b: [u8; 1] = [0]; loop { let mut buf: Vec<u8> = Vec::with_capacity(16); loop { let res = stdin.read(&mut u8b); if res.unwrap_or(0) == 0 || u8b[0] <= b' ' { break; } else { buf.push(u8b[0]); } } if buf.len() >= 1 { let ret = String::from_utf8(buf).unwrap(); return ret; } } } #[allow(dead_code)] fn get<T: std::str::FromStr>() -> T { get_word().parse().ok().unwrap() } /** * Lazy Segment Tree. This data structure is useful for fast folding and updating on intervals of an array * whose elements are elements of monoid T. Note that constructing this tree requires the identity * element of T and the operation of T. This is monomorphised, because of efficiency. T := i64, biop = max, upop = (+) * Reference: http://d.hatena.ne.jp/kyuridenamida/20121114/1352835261 * Verified by https://codeforces.com/contest/1114/submission/49759034 */ pub trait ActionRing { type T: Clone + Copy; // data type U: Clone + Copy + PartialEq + Eq; // action fn biop(x: Self::T, y: Self::T) -> Self::T; fn update(x: Self::T, a: Self::U, height: usize) -> Self::T; fn upop(fst: Self::U, snd: Self::U) -> Self::U; fn e() -> Self::T; fn upe() -> Self::U; // identity for upop } pub struct LazySegTree<R: ActionRing> { n: usize, dep: usize, dat: Vec<R::T>, lazy: Vec<R::U>, } impl<R: ActionRing> LazySegTree<R> { pub fn new(n_: usize) -> Self { let mut n = 1; let mut dep = 0; while n < n_ { n *= 2; dep += 1; } // n is a power of 2 LazySegTree { n: n, dep: dep, dat: vec![R::e(); 2 * n - 1], lazy: vec![R::upe(); 2 * n - 1] } } #[inline] fn lazy_evaluate_node(&mut self, k: usize, height: usize) { if self.lazy[k] == R::upe() { return; } self.dat[k] = R::update(self.dat[k], self.lazy[k], height); if k < self.n - 1 { self.lazy[2 * k + 1] = R::upop(self.lazy[2 * k + 1], self.lazy[k]); self.lazy[2 * k + 2] = R::upop(self.lazy[2 * k + 2], self.lazy[k]); } self.lazy[k] = R::upe(); // identity for upop } #[inline] fn update_node(&mut self, k: usize) { self.dat[k] = R::biop(self.dat[2 * k + 1], self.dat[2 * k + 2]); } fn update_sub(&mut self, a: usize, b: usize, v: R::U, k: usize, height: usize, l: usize, r: usize) { self.lazy_evaluate_node(k, height); // [a,b) and [l,r) intersects? if r <= a || b <= l {return;} if a <= l && r <= b { self.lazy[k] = R::upop(self.lazy[k], v); self.lazy_evaluate_node(k, height); return; } self.update_sub(a, b, v, 2 * k + 1, height - 1, l, (l + r) / 2); self.update_sub(a, b, v, 2 * k + 2, height - 1, (l + r) / 2, r); self.update_node(k); } /* ary[i] = upop(ary[i], v) for i in [a, b) (half-inclusive) */ #[inline] pub fn update(&mut self, a: usize, b: usize, v: R::U) { let n = self.n; let dep = self.dep; self.update_sub(a, b, v, 0, dep, 0, n); } /* l,r are for simplicity */ fn query_sub(&mut self, a: usize, b: usize, k: usize, height: usize, l: usize, r: usize) -> R::T { self.lazy_evaluate_node(k, height); // [a,b) and [l,r) intersect? if r <= a || b <= l {return R::e();} if a <= l && r <= b {return self.dat[k];} let vl = self.query_sub(a, b, 2 * k + 1, height - 1, l, (l + r) / 2); let vr = self.query_sub(a, b, 2 * k + 2, height - 1, (l + r) / 2, r); self.update_node(k); R::biop(vl, vr) } /* [a, b) (note: half-inclusive) */ #[inline] pub fn query(&mut self, a: usize, b: usize) -> R::T { let n = self.n; let dep = self.dep; self.query_sub(a, b, 0, dep, 0, n) } } enum Affine {} impl ActionRing for Affine { type T = [i64; 3]; // data type U = i64; // action, x |-> (1 a a^2) |-> (1 a+x (a+x)^2) fn biop(x: Self::T, y: Self::T) -> Self::T { let mut z = [0; 3]; for i in 0..3 { z[i] = x[i] + y[i]; } z } fn update(a: Self::T, add: Self::U, height: usize) -> Self::T { let add = add << height; let mut z = a; z[1] += a[0] * add; z[2] += a[0] * add * add; z[2] += a[1] * 2 * add; z } fn upop(fst: Self::U, snd: Self::U) -> Self::U { fst + snd } fn e() -> Self::T { [1, 0, 0] } fn upe() -> Self::U { // identity for upop 0 } } fn solve() { let out = std::io::stdout(); let mut out = BufWriter::new(out.lock()); macro_rules! puts { ($($format:tt)*) => (let _ = write!(out,$($format)*);); } let n: usize = get(); let a: Vec<i64> = (0..n).map(|_| get()).collect(); let mut st = LazySegTree::<Affine>::new(n); for i in 0..n { st.update(i, i + 1, a[i]); } let q: usize = get(); for _ in 0..q { let ty: i32 = get(); let l = get::<usize>() - 1; let r = get::<usize>(); if ty == 1 { let x: i64 = get(); st.update(l, r, x); } else { let z = st.query(l, r); puts!("{}\n", z[2]); } } } fn main() { // In order to avoid potential stack overflow, spawn a new thread. let stack_size = 104_857_600; // 100 MB let thd = std::thread::Builder::new().stack_size(stack_size); thd.spawn(|| solve()).unwrap().join().unwrap(); }