結果

問題 No.789 範囲の合計
ユーザー siro53
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #

// 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 {}
    }
}
0