結果
| 問題 |
No.776 A Simple RMQ Problem
|
| コンテスト | |
| ユーザー |
 Haar
|
| 提出日時 | 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);
}
}