結果
問題 |
No.789 範囲の合計
|
ユーザー |
|
提出日時 | 2025-10-19 11:13:52 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 173 ms / 1,000 ms |
コード長 | 12,239 bytes |
コンパイル時間 | 15,034 ms |
コンパイル使用メモリ | 400,024 KB |
実行使用メモリ | 34,688 KB |
最終ジャッジ日時 | 2025-10-19 11:14:22 |
合計ジャッジ時間 | 18,988 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 15 |
ソースコード
// verification-helper: PROBLEM https://yukicoder.me/problems/no/789 pub use __cargo_equip::prelude::*; use dynamic_segment_tree::DynamicSegmentTree; use monoid::add::Additive; use proconio::{fastout, input}; type DynamicSegTree = DynamicSegmentTree<Additive<i64>, 0, 1_000_000_002>; #[fastout] fn main() { input! { q: usize }; let mut seg = DynamicSegTree::new(); let mut ans = 0_i64; for _ in 0..q { input! { t: usize }; match t { 0 => { input! { x: i64, y: i64 }; seg.set(x, seg.get(x) + y); } 1 => { input! { l: i64, r: i64 } ans += seg.prod(l..=r); } _ => unreachable!(), } } println!("{}", ans); } // The following code was expanded by `cargo-equip`. /// # Bundled libraries /// /// - `path+file:///home/siro53/repos/comprolib_rs/crates/ds/segment_tree/dynamic_segment_tree#0.1.0` published in **missing** licensed under **missing** as `crate::__cargo_equip::crates::dynamic_segment_tree` /// - `path+file:///home/siro53/repos/comprolib_rs/crates/traits/monoid#0.1.0` published in **missing** licensed under **missing** as `crate::__cargo_equip::crates::monoid` /// - `path+file:///home/siro53/repos/comprolib_rs/crates/traits/numeric#0.1.0` published in **missing** licensed under **missing** as `crate::__cargo_equip::crates::__numeric_0_1_0` #[cfg_attr(any(), rustfmt::skip)] #[allow(unused)] mod __cargo_equip { pub(crate) mod crates { pub mod dynamic_segment_tree {use crate::__cargo_equip::preludes::dynamic_segment_tree::*;use std::ops::{Bound,RangeBounds};use monoid::Monoid;pub struct Node<M>where M:Monoid,{value:M::ValueType,children_node:[Option<Box<Node<M>>>;2],}impl<M>Node<M>where M:Monoid,{pub fn new(value:M::ValueType)->Self{Self{value,children_node:[None,None],}}}pub struct DynamicSegmentTree<M,const MIN_INDEX:i64,const MAX_INDEX:i64>where M:Monoid,{root:Option<Box<Node<M>>>,}impl<M,const MIN_INDEX:i64,const MAX_INDEX:i64>Default for DynamicSegmentTree<M,MIN_INDEX,MAX_INDEX>where M:Monoid,{fn default()->Self{Self{root:None}}}impl<M,const MIN_INDEX:i64,const MAX_INDEX:i64>DynamicSegmentTree<M,MIN_INDEX,MAX_INDEX>where M:Monoid,{pub fn new()->Self{Self::default()}pub fn set(&mut self,pos:i64,value:M::ValueType){assert!(MIN_INDEX<=pos);assert!(pos<MAX_INDEX);Self::_set(&mut self.root,MIN_INDEX,MAX_INDEX,pos,value);}pub fn get(&self,pos:i64)->M::ValueType{assert!(MIN_INDEX<=pos);assert!(pos<MAX_INDEX);Self::_get(&self.root,MIN_INDEX,MAX_INDEX,pos)}pub fn prod<R:RangeBounds<i64>>(&self,range:R)->M::ValueType{let l=match range.start_bound(){Bound::Included(l)=>*l,Bound::Excluded(l)=>l+1,Bound::Unbounded=>MIN_INDEX,};let r=match range.end_bound(){Bound::Included(r)=>r+1,Bound::Excluded(r)=>*r,Bound::Unbounded=>MAX_INDEX,};assert!(MIN_INDEX<=l);assert!(l<=r);assert!(r<=MAX_INDEX);Self::_prod(&self.root,MIN_INDEX,MAX_INDEX,l,r)}fn _set(node:&mut Option<Box<Node<M>>>,l:i64,r:i64,pos:i64,value:M::ValueType){if node.is_none(){*node=Some(Box::new(Node::<M>::new(M::unit())));}let ptr=node.as_mut().unwrap();if r-l==1{ptr.value=value;return;}let mid=(l+r)/2;if pos<mid{Self::_set(&mut ptr.children_node[0],l,mid,pos,value);}else{Self::_set(&mut ptr.children_node[1],mid,r,pos,value);}let left_value=if ptr.children_node[0].is_none(){M::unit()}else{ptr.children_node[0].as_mut().unwrap().value.clone()};let right_value=if ptr.children_node[1].is_none(){M::unit()}else{ptr.children_node[1].as_mut().unwrap().value.clone()};ptr.value=M::op(&left_value,&right_value);}fn _get(node:&Option<Box<Node<M>>>,l:i64,r:i64,pos:i64)->M::ValueType{if node.is_none(){return M::unit();}let ptr=node.as_ref().unwrap();if r-l==1{return ptr.value.clone();}let mid=(l+r)/2;if pos<mid{Self::_get(&ptr.children_node[0],l,mid,pos)}else{Self::_get(&ptr.children_node[1],mid,r,pos)}}fn _prod(node:&Option<Box<Node<M>>>,l:i64,r:i64,ql:i64,qr:i64)->M::ValueType{if node.is_none()||(qr<=l||r<=ql){return M::unit();}let ptr=node.as_ref().unwrap();if ql<=l&&r<=qr{return ptr.value.clone();}let mid=(l+r)/2;M::op(&Self::_prod(&ptr.children_node[0],l,mid,ql,qr),&Self::_prod(&ptr.children_node[1],mid,r,ql,qr),)}}} pub mod monoid {use crate::__cargo_equip::preludes::monoid::*;pub trait Monoid{type ValueType:Clone;fn op(left_value:&Self::ValueType,right_value:&Self::ValueType)->Self::ValueType;fn unit()->Self::ValueType;}pub mod add{use crate::__cargo_equip::preludes::monoid::*;use std::{marker::PhantomData,ops::Add};use crate::__cargo_equip::crates::monoid::Monoid;use numeric::zero::Zero;pub struct Additive<T>(PhantomData<fn()->T>);impl<T>Monoid for Additive<T>where T:Add<Output=T>+Copy+Zero,{type ValueType=T;fn op(left_value:&Self::ValueType,right_value:&Self::ValueType)->Self::ValueType{*left_value+*right_value}fn unit()->Self::ValueType{T::zero()}}}pub mod affine{use crate::__cargo_equip::preludes::monoid::*;use std::{marker::PhantomData,ops::{Add,Mul},};use crate::__cargo_equip::crates::monoid::Monoid;use numeric::{one::One,zero::Zero};#[derive(Clone)]pub struct Affine<T>(pub T,pub T);impl<T>Affine<T>where T:Clone+Add<Output=T>+Mul<Output=T>,{pub fn eval(self,x:T)->T{self.0*x+self.1}}pub struct AffineOperator<T,const REV:bool=false>(PhantomData<fn()->T>);impl<T,const REV:bool>Monoid for AffineOperator<T,REV>where T:Copy+Add<Output=T>+Mul<Output=T>+Zero+One,{type ValueType=Affine<T>;fn op(left_value:&Self::ValueType,right_value:&Self::ValueType)->Self::ValueType{if REV{return Affine(right_value.0*left_value.0,right_value.0*left_value.1+right_value.1,);}Affine(left_value.0*right_value.0,left_value.0*right_value.1+left_value.1,)}fn unit()->Self::ValueType{Affine(T::one(),T::zero())}}}pub mod bitwise_and{use crate::__cargo_equip::preludes::monoid::*;use std::{marker::PhantomData,ops::{BitAnd,Not},};use crate::__cargo_equip::crates::monoid::Monoid;use numeric::zero::Zero;pub struct BitwiseAnd<T>(PhantomData<fn()->T>);impl<T>Monoid for BitwiseAnd<T>where T:Copy+BitAnd<Output=T>+Not<Output=T>+Zero,{type ValueType=T;fn op(left_value:&Self::ValueType,right_value:&Self::ValueType)->Self::ValueType{*left_value&*right_value}fn unit()->Self::ValueType{!T::zero()}}}pub mod bitwise_or{use crate::__cargo_equip::preludes::monoid::*;use std::{marker::PhantomData,ops::BitOr};use crate::__cargo_equip::crates::monoid::Monoid;use numeric::zero::Zero;pub struct BitwiseOr<T>(PhantomData<fn()->T>);impl<T>Monoid for BitwiseOr<T>where T:Copy+BitOr<Output=T>+Zero,{type ValueType=T;fn op(left_value:&Self::ValueType,right_value:&Self::ValueType)->Self::ValueType{*left_value|*right_value}fn unit()->Self::ValueType{T::zero()}}}pub mod bitwise_xor{use crate::__cargo_equip::preludes::monoid::*;use std::{marker::PhantomData,ops::BitXor};use crate::__cargo_equip::crates::monoid::Monoid;use numeric::zero::Zero;pub struct BitwiseXor<T>(PhantomData<fn()->T>);impl<T>Monoid for BitwiseXor<T>where T:Copy+BitXor<Output=T>+Zero,{type ValueType=T;fn op(left_value:&Self::ValueType,right_value:&Self::ValueType)->Self::ValueType{*left_value^*right_value}fn unit()->Self::ValueType{T::zero()}}}pub mod max{use crate::__cargo_equip::preludes::monoid::*;use std::marker::PhantomData;use crate::__cargo_equip::crates::monoid::Monoid;use numeric::bound::BoundedBelow;pub struct Max<T>(PhantomData<fn()->T>);impl<T>Monoid for Max<T>where T:Copy+Ord+BoundedBelow,{type ValueType=T;fn op(left_value:&Self::ValueType,right_value:&Self::ValueType)->Self::ValueType{std::cmp::max(*left_value,*right_value)}fn unit()->Self::ValueType{T::min_value()}}}pub mod max_with_index{use crate::__cargo_equip::preludes::monoid::*;use std::marker::PhantomData;use crate::__cargo_equip::crates::monoid::Monoid;use numeric::bound::BoundedBelow;#[derive(Clone,Copy)]#[allow(unused)]pub struct MaxWithIndex<T>{max_value:T,max_index:usize,}pub struct MaxWithIndexOperator<T>(PhantomData<fn()->T>);impl<T>Monoid for MaxWithIndexOperator<T>where T:Copy+Ord+BoundedBelow,{type ValueType=MaxWithIndex<T>;fn op(left_value:&Self::ValueType,right_value:&Self::ValueType)->Self::ValueType{if left_value.max_value<right_value.max_value{*right_value}else{*left_value}}fn unit()->Self::ValueType{MaxWithIndex{max_value:T::min_value(),max_index:0,}}}}pub mod min{use crate::__cargo_equip::preludes::monoid::*;use std::marker::PhantomData;use crate::__cargo_equip::crates::monoid::Monoid;use numeric::bound::BoundedAbove;pub struct Min<T>(PhantomData<fn()->T>);impl<T>Monoid for Min<T>where T:Copy+Ord+BoundedAbove,{type ValueType=T;fn op(left_value:&Self::ValueType,right_value:&Self::ValueType)->Self::ValueType{std::cmp::min(*left_value,*right_value)}fn unit()->Self::ValueType{T::max_value()}}}pub mod min_with_index{use crate::__cargo_equip::preludes::monoid::*;use std::marker::PhantomData;use crate::__cargo_equip::crates::monoid::Monoid;use numeric::bound::BoundedAbove;#[derive(Clone,Copy)]#[allow(unused)]pub struct MinWithIndex<T>{min_value:T,min_index:usize,}pub struct MinWithIndexOperator<T>(PhantomData<fn()->T>);impl<T>Monoid for MinWithIndexOperator<T>where T:Copy+Ord+BoundedAbove,{type ValueType=MinWithIndex<T>;fn op(left_value:&Self::ValueType,right_value:&Self::ValueType)->Self::ValueType{if left_value.min_value>right_value.min_value{*right_value}else{*left_value}}fn unit()->Self::ValueType{MinWithIndex{min_value:T::max_value(),min_index:0,}}}}pub mod mul{use crate::__cargo_equip::preludes::monoid::*;use std::{marker::PhantomData,ops::Mul};use crate::__cargo_equip::crates::monoid::Monoid;use numeric::one::One;pub struct Multiplicative<T>(PhantomData<fn()->T>);impl<T>Monoid for Multiplicative<T>where T:Mul<Output=T>+Copy+One,{type ValueType=T;fn op(left_value:&Self::ValueType,right_value:&Self::ValueType)->Self::ValueType{*left_value**right_value}fn unit()->Self::ValueType{T::one()}}}} pub mod __numeric_0_1_0 {pub mod bound{pub trait BoundedBelow{fn min_value()->Self;}pub trait BoundedAbove{fn max_value()->Self;}macro_rules!impl_bound_integer{($($ty:ty),*)=>{$(impl BoundedBelow for$ty{#[inline]fn min_value()->Self{Self::MIN}}impl BoundedAbove for$ty{#[inline]fn max_value()->Self{Self::MAX}})*};}impl_bound_integer!(i8,i16,i32,i64,i128,isize,u8,u16,u32,u64,u128,usize);}pub mod infinity{pub trait Infinity{fn infinity()->Self;}pub trait NegInfinity{fn negative_infinity()->Self;}macro_rules!impl_infinity{($($t:ty,$infinity_value:expr,)*)=>{$(impl Infinity for$t{fn infinity()->Self{$infinity_value}})*}}macro_rules!impl_negative_infinity{($($t:ty,$neg_infinity_value:expr,)*)=>{$(impl NegInfinity for$t{fn negative_infinity()->Self{$neg_infinity_value}})*}}impl_infinity!{i32,1_i32<<30,u32,1_u32<<30,f32,1e10,i64,1_i64<<60,isize,1_isize<<60,u64,1_u64<<60,usize,1_usize<<60,f64,1e20,i128,1_i128<<120,u128,1_u128<<120,}impl_negative_infinity!{i32,-1_i32<<30,u32,0,f32,-1e10,i64,-1_i64<<60,isize,-1_isize<<60,u64,0,usize,0,f64,1e20,i128,-1_i128<<120,u128,0,}}pub mod one{pub trait One{fn one()->Self;}macro_rules!impl_one_integer{($($ty:ty),*)=>{$(impl One for$ty{#[inline]fn one()->Self{1}})*};}macro_rules!impl_one_float{($($ty:ty),*)=>{$(impl One for$ty{#[inline]fn one()->Self{1.}})*};}impl_one_integer!(u8,u16,u32,u64,u128,usize,i8,i16,i32,i64,i128,isize);impl_one_float!(f32,f64);}pub mod zero{pub trait Zero{fn zero()->Self;}macro_rules!impl_zero_integer{($($ty:ty),*)=>{$(impl Zero for$ty{#[inline]fn zero()->Self{0}})*};}macro_rules!impl_zero_float{($($ty:ty),*)=>{$(impl Zero for$ty{#[inline]fn zero()->Self{0.}})*};}impl_zero_integer!(u8,u16,u32,u64,u128,usize,i8,i16,i32,i64,i128,isize);impl_zero_float!(f32,f64);}} } pub(crate) mod macros { pub mod dynamic_segment_tree {} pub mod monoid {} pub mod __numeric_0_1_0 {} } pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;} mod preludes { pub mod dynamic_segment_tree {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::monoid;} pub mod monoid {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::__numeric_0_1_0 as numeric;} pub mod __numeric_0_1_0 {} } }