結果
問題 |
No.776 A Simple RMQ Problem
|
ユーザー |
|
提出日時 | 2025-04-10 23:49:41 |
言語 | Rust (1.83.0 + proconio) |
結果 |
WA
|
実行時間 | - |
コード長 | 17,091 bytes |
コンパイル時間 | 13,901 ms |
コンパイル使用メモリ | 388,124 KB |
実行使用メモリ | 14,596 KB |
最終ジャッジ日時 | 2025-04-10 23:50:14 |
合計ジャッジ時間 | 20,850 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 17 WA * 9 |
コンパイルメッセージ
warning: variable does not need to be mutable --> src/main.rs:54:29 | 54 | let mut ret = seg.fold(l1..l2).right_max | ----^^^ | | | help: remove this `mut` | = note: `#[warn(unused_mut)]` on by default
ソースコード
// Bundled at 2025/04/10 23:49:21 +09:00 // Author: Haar pub mod main { use super::*; #[allow(unused_imports)] use haar_lib::{get, input, io::fastio::*, iter::join_str::*}; #[allow(unused_imports)] use std::cell::{Cell, RefCell}; #[allow(unused_imports)] use std::cmp::{max, min, Reverse}; #[allow(unused_imports)] use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque}; #[allow(unused_imports)] use std::io::Write; #[allow(unused_imports)] use std::mem::swap; #[allow(unused_imports)] use std::rc::Rc; #[derive(Clone, Default)] pub struct Problem {} use haar_lib::algebra::max_partial_sum::*; use haar_lib::ds::segtree::*; impl Problem { pub fn init() -> Self { Self {} } pub fn main(&mut self) -> Result<(), Box<dyn std::error::Error>> { let mut io = FastIO::new(); let n = io.read_usize(); let q = io.read_usize(); let m = MaxPartialSum::<i64>::new(); let mut seg = Segtree::new(n, m); let mut a = get!(io, [i64; n]); for i in 0..n { seg.assign(i, MaxPartialSumValue::new(a[i])); } for _ in 0..q { let query = io.read_bytes(); if query == b"set" { let i = io.read_usize() - 1; let x = io.read_i64(); seg.assign(i, MaxPartialSumValue::new(x)); a[i] = x; } else { let l1 = io.read_usize() - 1; let l2 = io.read_usize() - 1; let r1 = io.read_usize() - 1; let r2 = io.read_usize() - 1; let r1 = r1.max(l1); let l2 = l2.min(r2); let mut ans = i64::MIN; let f = |l1, l2, r1, r2| { let mut ret = seg.fold(l1..l2).right_max + seg.fold(min(l2, r1)..r1 + 1).sum + seg.fold(r1 + 1..r2 + 1).left_max; ret }; if l2 <= r1 { ans = f(l1, l2, r1, r2); } else { if l1 <= r1 { ans = ans.max(f(l1, r1, r1, r2)); } if l2 <= r2 { ans = ans.max(f(l1, l2, l2, r2)); } if r1 <= l2 { ans = ans.max(seg.fold(r1..l2 + 1).partial_max); } } io.writeln(ans); } } Ok(()) } } } fn main() { main::Problem::init().main().unwrap(); } use crate as haar_lib; pub mod algebra { pub mod traits { use crate::trait_alias; pub trait Set { type Element; } pub trait BinaryOp: Set { fn op(&self, _: Self::Element, _: Self::Element) -> Self::Element; } pub trait Identity: Set { fn id(&self) -> Self::Element; } pub trait Inverse: Set { fn inv(&self, _: Self::Element) -> Self::Element; } pub trait Commutative {} pub trait Associative {} pub trait Idempotence {} trait_alias!(#[doc = "半群"]Semigroup:BinaryOp+Associative); trait_alias!(#[doc = "モノイド"]Monoid:Semigroup+Identity); trait_alias!(#[doc = "可換モノイド"]AbelianMonoid:Monoid+Commutative); trait_alias!(#[doc = "群"]Group:Monoid + Inverse); trait_alias!(#[doc = "可換群"]AbelianGroup:Group+Commutative); pub trait Times: BinaryOp + Identity where Self::Element: Clone, { fn times(&self, mut a: Self::Element, mut n: u64) -> Self::Element { let mut ret = self.id(); while n > 0 { if n & 1 == 1 { ret = self.op(ret, a.clone()); } a = self.op(a.clone(), a); n >>= 1; } ret } } impl<A: BinaryOp + Identity> Times for A where Self::Element: Clone {} } pub mod max_partial_sum { pub use crate::algebra::traits::*; use crate::max; use crate::num::one_zero::Zero; use std::marker::PhantomData; use std::ops::Add; #[derive(Clone, Copy, Default, Debug, PartialEq, Eq)] pub struct MaxPartialSumValue<T> { pub sum: T, pub left_max: T, pub right_max: T, pub partial_max: T, } impl<T: Copy> MaxPartialSumValue<T> { pub fn new(value: T) -> Self { Self { sum: value, left_max: value, right_max: value, partial_max: value, } } } #[derive(Clone, Copy, Default, Debug, PartialEq, Eq)] pub struct MaxPartialSum<T>(PhantomData<T>); impl<T> MaxPartialSum<T> { pub fn new() -> Self { Self(PhantomData) } } impl<T> Set for MaxPartialSum<T> { type Element = MaxPartialSumValue<T>; } impl<T: Copy + Zero> Identity for MaxPartialSum<T> { fn id(&self) -> Self::Element { MaxPartialSumValue::new(T::zero()) } } impl<T: Copy + Ord + Add<Output = T>> BinaryOp for MaxPartialSum<T> { fn op(&self, a: Self::Element, b: Self::Element) -> Self::Element { MaxPartialSumValue { sum: a.sum + b.sum, left_max: a.left_max.max(a.sum + b.left_max), right_max: b.right_max.max(b.sum + a.right_max), partial_max: max!(a.partial_max, b.partial_max, a.right_max + b.left_max), } } } impl<T> Associative for MaxPartialSum<T> {} } } pub mod ds { pub mod segtree { pub use crate::algebra::traits::Monoid; use crate::misc::range::range_bounds_to_range; use std::ops::{Index, RangeBounds}; #[derive(Clone)] pub struct Segtree<M: Monoid> { original_size: usize, size: usize, data: Vec<M::Element>, monoid: M, } impl<M: Monoid> Segtree<M> where M::Element: Clone, { pub fn new(n: usize, monoid: M) -> Self { let size = n.next_power_of_two() * 2; Segtree { original_size: n, size, data: vec![monoid.id(); size], monoid, } } pub fn fold<R: RangeBounds<usize>>(&self, range: R) -> M::Element { let (l, r) = range_bounds_to_range(range, 0, self.size / 2); let mut ret_l = self.monoid.id(); let mut ret_r = self.monoid.id(); let mut l = l + self.size / 2; let mut r = r + self.size / 2; while l < r { if r & 1 == 1 { r -= 1; ret_r = self.monoid.op(self.data[r].clone(), ret_r); } if l & 1 == 1 { ret_l = self.monoid.op(ret_l, self.data[l].clone()); l += 1; } r >>= 1; l >>= 1; } self.monoid.op(ret_l, ret_r) } pub fn assign(&mut self, i: usize, value: M::Element) { let mut i = i + self.size / 2; self.data[i] = value; while i > 1 { i >>= 1; self.data[i] = self .monoid .op(self.data[i << 1].clone(), self.data[(i << 1) | 1].clone()); } } pub fn update(&mut self, i: usize, value: M::Element) { self.assign( i, self.monoid.op(self.data[i + self.size / 2].clone(), value), ); } } impl<M: Monoid> From<&Segtree<M>> for Vec<M::Element> where M::Element: Clone, { fn from(from: &Segtree<M>) -> Self { from.data[from.size / 2..from.size / 2 + from.original_size].to_vec() } } impl<M: Monoid> Index<usize> for Segtree<M> { type Output = M::Element; fn index(&self, i: usize) -> &Self::Output { &self.data[self.size / 2 + i] } } } } pub mod io { pub mod fastio { use std::fmt::Display; use std::io::{Read, Write}; pub struct FastIO { in_bytes: Vec<u8>, in_cur: usize, out_buf: std::io::BufWriter<std::io::Stdout>, } impl FastIO { pub fn new() -> Self { let mut s = vec![]; std::io::stdin().read_to_end(&mut s).unwrap(); let cout = std::io::stdout(); Self { in_bytes: s, in_cur: 0, out_buf: std::io::BufWriter::new(cout), } } #[inline] pub fn getc(&mut self) -> Option<u8> { let c = *self.in_bytes.get(self.in_cur)?; self.in_cur += 1; Some(c) } #[inline] pub fn peek(&self) -> Option<u8> { Some(*self.in_bytes.get(self.in_cur)?) } #[inline] pub fn skip(&mut self) { while self.peek().is_some_and(|c| c.is_ascii_whitespace()) { self.in_cur += 1; } } pub fn read_u64(&mut self) -> u64 { self.skip(); let mut ret: u64 = 0; while self.peek().is_some_and(|c| c.is_ascii_digit()) { ret = ret * 10 + (self.in_bytes[self.in_cur] - b'0') as u64; self.in_cur += 1; } ret } pub fn read_u32(&mut self) -> u32 { self.read_u64() as u32 } pub fn read_usize(&mut self) -> usize { self.read_u64() as usize } pub fn read_i64(&mut self) -> i64 { self.skip(); let mut ret: i64 = 0; let minus = if self.peek() == Some(b'-') { self.in_cur += 1; true } else { false }; while self.peek().is_some_and(|c| c.is_ascii_digit()) { ret = ret * 10 + (self.in_bytes[self.in_cur] - b'0') as i64; self.in_cur += 1; } if minus { ret = -ret; } ret } pub fn read_i32(&mut self) -> i32 { self.read_i64() as i32 } pub fn read_isize(&mut self) -> isize { self.read_i64() as isize } pub fn read_f64(&mut self) -> f64 { self.read_chars() .into_iter() .collect::<String>() .parse() .unwrap() } pub fn read_chars(&mut self) -> Vec<char> { self.skip(); let mut ret = vec![]; while self.peek().is_some_and(|c| c.is_ascii_graphic()) { ret.push(self.in_bytes[self.in_cur] as char); self.in_cur += 1; } ret } pub fn read_bytes(&mut self) -> Vec<u8> { self.skip(); let mut ret = vec![]; while self.peek().is_some_and(|c| c.is_ascii_graphic()) { ret.push(self.in_bytes[self.in_cur]); self.in_cur += 1; } ret } pub fn write<T: Display>(&mut self, s: T) { self.out_buf.write_all(format!("{}", s).as_bytes()).unwrap(); } pub fn writeln<T: Display>(&mut self, s: T) { self.write(s); self.out_buf.write_all(b"\n").unwrap(); } } impl Drop for FastIO { fn drop(&mut self) { self.out_buf.flush().unwrap(); } } } } pub mod iter { pub mod join_str { pub trait JoinStr: Iterator { fn join_str(self, s: &str) -> String where Self: Sized, Self::Item: ToString, { self.map(|x| x.to_string()).collect::<Vec<_>>().join(s) } } impl<I> JoinStr for I where I: Iterator + ?Sized {} } } pub mod macros { pub mod io { #[macro_export] macro_rules! get { ( $in:ident, [$a:tt $(as $to:ty)*; $num:expr] ) => { { let n = $num; (0 .. n).map(|_| get!($in, $a $(as $to)*)).collect::<Vec<_>>() } }; ( $in:ident, ($($type:tt $(as $to:ty)*),*) ) => { ($(get!($in, $type $(as $to)*)),*) }; ( $in:ident, i8 ) => { $in.read_i64() as i8 }; ( $in:ident, i16 ) => { $in.read_i64() as i16 }; ( $in:ident, i32 ) => { $in.read_i64() as i32 }; ( $in:ident, i64 ) => { $in.read_i64() }; ( $in:ident, isize ) => { $in.read_i64() as isize }; ( $in:ident, u8 ) => { $in.read_u64() as u8 }; ( $in:ident, u16 ) => { $in.read_u64() as u16 }; ( $in:ident, u32 ) => { $in.read_u64() as u32 }; ( $in:ident, u64 ) => { $in.read_u64() }; ( $in:ident, usize ) => { $in.read_u64() as usize }; ( $in:ident, [char] ) => { $in.read_chars() }; ( $in:ident, $from:tt as $to:ty ) => { <$to>::from(get!($in, $from)) }; } #[macro_export] macro_rules! input { ( @inner $in:ident, mut $name:ident : $type:tt ) => { let mut $name = get!($in, $type); }; ( @inner $in:ident, mut $name:ident : $type:tt as $to:ty ) => { let mut $name = get!($in, $type as $to); }; ( @inner $in:ident, $name:ident : $type:tt ) => { let $name = get!($in, $type); }; ( @inner $in:ident, $name:ident : $type:tt as $to:ty ) => { let $name = get!($in, $type as $to); }; ( $in:ident >> $($($names:ident)* : $type:tt $(as $to:ty)*),* ) => { $(input!(@inner $in, $($names)* : $type $(as $to)*);)* } } } pub mod max_min { #[macro_export] macro_rules! max { ($x:expr, $($xs:expr),*) => { { let mut ret = $x; for &x in &[$($xs),*] { if x > ret { ret = x } } ret } } } #[macro_export] macro_rules! min { ($x:expr, $($xs:expr),*) => { { let mut ret = $x; for &x in &[$($xs),*] { if x < ret { ret = x } } ret } } } } pub mod trait_alias { #[macro_export] macro_rules! trait_alias { ($(#[$meta:meta])* $name:ident: $($t:tt)+) => { $(#[$meta])* pub trait $name : $($t)+ {} impl<T: $($t)+> $name for T {} }; } } } pub mod misc { pub mod range { use std::ops::RangeBounds; pub fn range_bounds_to_range<R: RangeBounds<usize>>( r: R, start: usize, end: usize, ) -> (usize, usize) { use std::ops::Bound::*; let l = match r.start_bound() { Included(&l) => l, Excluded(&l) => l + 1, Unbounded => start, } .max(start); let r = match r.end_bound() { Included(&r) => r + 1, Excluded(&r) => r, Unbounded => end, } .min(end); (l, r) } } } pub mod num { pub mod one_zero { pub trait Zero { fn zero() -> Self; } pub trait One { fn one() -> Self; } macro_rules! impl_one_zero { ($($t:ty),*) => { $( impl Zero for $t { fn zero() -> Self { 0 as $t } } impl One for $t { fn one() -> Self { 1 as $t } } )* } } impl_one_zero!(u8, u16, u32, u64, u128, usize, i8, i16, i32, i64, i128, isize, f32, f64); } }