Submit Info #23061

Problem Lang User Status Time Memory
Range Chmin Chmax Add Range Sum rust sansen AC 223 ms 21.55 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.61 MiB
max_random_00 AC 210 ms 21.45 MiB
max_random_01 AC 223 ms 21.55 MiB
max_random_02 AC 223 ms 21.54 MiB
medium_00 AC 2 ms 0.67 MiB
medium_01 AC 1 ms 0.60 MiB
medium_02 AC 1 ms 0.60 MiB
random_00 AC 137 ms 11.29 MiB
random_01 AC 156 ms 21.30 MiB
random_02 AC 95 ms 6.05 MiB
small_00 AC 0 ms 0.62 MiB
small_01 AC 0 ms 0.56 MiB
small_02 AC 2 ms 0.62 MiB
small_03 AC 0 ms 0.61 MiB
small_04 AC 1 ms 0.62 MiB
small_05 AC 0 ms 0.64 MiB
small_06 AC 0 ms 0.63 MiB
small_07 AC 1 ms 0.62 MiB
small_08 AC 2 ms 0.62 MiB
small_09 AC 1 ms 0.62 MiB

// 嘘解法 // ---------- begin Scanner(require delimiter) ---------- mod scanner { pub struct Scanner<R> { reader: R, buf: Vec<u8>, } #[allow(dead_code)] impl<R: std::io::BufRead> Scanner<R> { pub fn new(reader: R) -> Self { Scanner { reader: reader, buf: Vec::with_capacity(1024), } } fn read(&mut self, del: u8) { self.buf.clear(); self.reader.read_until(del, &mut self.buf).ok(); assert!(self.buf.pop().unwrap() == del); } pub fn next<T: std::str::FromStr>(&mut self, del: u8) -> T { self.read(del); std::str::from_utf8(&self.buf) .unwrap() .trim() .parse::<T>() .ok() .unwrap() } pub fn next_bytes(&mut self, del: u8) -> Vec<u8> { self.read(del); std::str::from_utf8(&self.buf) .unwrap() .trim() .bytes() .collect() } } } // ---------- end scanner(require delimiter) ---------- use std::io::Write; fn main() { let stdin = std::io::stdin(); let mut sc = scanner::Scanner::new(stdin.lock()); run(&mut sc); } use std::cmp::*; struct Node { max: i64, min: i64, add: i64, sum: i64, len: i64, } impl Node { fn one(v: i64) -> Self { Node { max: v, min: v, add: 0, sum: v, len: 1, } } fn fold(&self, rhs: &Self) -> Self { Node { max: max(self.max, rhs.max), min: min(self.min, rhs.min), add: 0, sum: self.sum + rhs.sum, len: self.len + rhs.len, } } fn update(&mut self, v: i64) { self.max = v; self.min = v; self.add = 0; self.sum = v * self.len; } fn add(&mut self, v: i64) { self.max += v; self.min += v; self.add += v; self.sum += v * self.len; } } fn propagate(k: usize, node: &mut [Node]) { let add = node[k].add; node[k].add = 0; let same = node[k].max == node[k].min; let v = node[k].max; for s in node[(2 * k)..].iter_mut().take(2) { if same { s.update(v); } else { s.add(add); } } } fn chmin(k: usize, l: usize, r: usize, x: usize, y: usize, v: i64, node: &mut [Node]) { if r <= x || y <= l || node[k].max <= v { return; } if x <= l && r <= y && node[k].min >= v { node[k].update(v); return; } propagate(k, node); let m = (l + r) / 2; chmin(2 * k , l, m, x, y, v, node); chmin(2 * k + 1, m, r, x, y, v, node); node[k] = node[2 * k].fold(&node[2 * k + 1]); } fn chmax(k: usize, l: usize, r: usize, x: usize, y: usize, v: i64, node: &mut [Node]) { if r <= x || y <= l || node[k].min >= v { return; } if x <= l && r <= y && node[k].max <= v { node[k].update(v); return; } propagate(k, node); let m = (l + r) / 2; chmax(2 * k , l, m, x, y, v, node); chmax(2 * k + 1, m, r, x, y, v, node); node[k] = node[2 * k].fold(&node[2 * k + 1]); } fn add(k: usize, l: usize, r: usize, x: usize, y: usize, v: i64, node: &mut [Node]) { if r <= x || y <= l { return; } if x <= l && r <= y { node[k].add(v); return; } propagate(k, node); let m = (l + r) / 2; add(2 * k , l, m, x, y, v, node); add(2 * k + 1, m, r, x, y, v, node); node[k] = node[2 * k].fold(&node[2 * k + 1]); } fn sum(k: usize, l: usize, r: usize, x: usize, y: usize, node: &mut [Node]) -> i64 { if r <= x || y <= l { return 0; } if x <= l && r <= y { return node[k].sum; } propagate(k, node); let m = (l + r) / 2; sum(2 * k, l, m, x, y, node) + sum(2 * k + 1, m, r, x, y, node) } fn run<R: std::io::BufRead>(sc: &mut scanner::Scanner<R>) { let out = std::io::stdout(); let mut out = std::io::BufWriter::new(out.lock()); let n: usize = sc.next(b' '); let q: usize = sc.next(b'\n'); let size = n.next_power_of_two(); let mut node = (0..(2 * size)).map(|_| Node::one(0)).collect::<Vec<_>>(); for (i, s) in node[size..].iter_mut().enumerate().take(n) { let d = if i == n - 1 { b'\n' } else { b' ' }; let v: i64 = sc.next(d); *s = Node::one(v); } for i in (1..size).rev() { node[i] = node[2 * i].fold(&node[2 * i + 1]); } for _ in 0..q { let op: u8 = sc.next(b' '); let l: usize = sc.next(b' '); let r: usize = sc.next(if op == 3 { b'\n' } else { b' ' }); let b: i64 = if op == 3 { 0 } else { sc.next(b'\n') }; if op == 0 { chmin(1, 0, size, l, r, b, &mut node); } else if op == 1 { chmax(1, 0, size, l, r, b, &mut node); } else if op == 2 { add(1, 0, size, l, r, b, &mut node); } else if op == 3 { let ans = sum(1, 0, size, l, r, &mut node); writeln!(out, "{}", ans).ok(); } else { unreachable!(); } } }