結果

問題 No.2761 Substitute and Search
ユーザー magurofly
提出日時 2024-05-01 05:28:38
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 1,034 ms / 4,000 ms
コード長 9,881 bytes
コンパイル時間 12,118 ms
コンパイル使用メモリ 396,232 KB
実行使用メモリ 90,760 KB
最終ジャッジ日時 2024-11-29 18:26:27
合計ジャッジ時間 19,456 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: variable `N` should have a snake case name
  --> src/main.rs:38:9
   |
38 |         N: usize, L: usize, Q: usize,
   |         ^ help: convert the identifier to snake case: `n`
   |
   = note: `#[warn(non_snake_case)]` on by default

warning: variable `L` should have a snake case name
  --> src/main.rs:38:19
   |
38 |         N: usize, L: usize, Q: usize,
   |                   ^ help: convert the identifier to snake case: `l`

warning: variable `Q` should have a snake case name
  --> src/main.rs:38:29
   |
38 |         N: usize, L: usize, Q: usize,
   |                             ^ help: convert the identifier to snake case: `q`

warning: variable `S` should have a snake case name
  --> src/main.rs:39:13
   |
39 |         mut S: [Chars; N],
   |             ^ help: convert the identifier to snake case (notice the capitalization): `s`

ソースコード

diff #
プレゼンテーションモードにする

pub use __cargo_equip::prelude::*;
use acl_segtree::*;
use proconio::{
    input,
    marker::{Chars, Usize1},
};
const MOD: u64 = (1 << 61) - 1;
const BASE: u64 = 0x1234567;
const fn mul(a: u64, b: u64) -> u64 {
    let (au, ad) = (a >> 31, a & (1 << 31) - 1);
    let (bu, bd) = (b >> 31, b & (1 << 31) - 1);
    let mid = ad * bu * au * bd;
    let (midu, midd) = (mid >> 30, mid & (1 << 30) - 1);
    modulo(au * bu * 2 + midu + (midd << 31) + ad * bd)
}
const fn modulo(x: u64) -> u64 {
    let mut res = (x >> 61) + (x & (1 << 61) - 1);
    if res >= MOD {
        res -= MOD;
    }
    res
}
const POW: [u64; 3000] = {
    let mut pow = [0; 3000];
    pow[0] = 1;
    let mut i = 1;
    while i < 3000 {
        pow[i] = mul(pow[i - 1], BASE);
        i += 1;
    }
    pow
};
fn main() {
    input! {
        N: usize, L: usize, Q: usize,
        mut S: [Chars; N],
    }
    struct M;
    impl Monoid for M {
        type S = u64;
        fn binary_operation(&x1: &Self::S, &x2: &Self::S) -> Self::S {
            modulo(x1 + x2)
        }
        fn identity() -> Self::S {
            0
        }
    }
    let mut hashes = S
        .iter()
        .map(|s| {
            Segtree::<M>::from(
                (0..L)
                    .map(|k| mul(POW[k], (s[k] as u8 - b'a' + 1) as u64))
                    .collect::<Vec<_>>(),
            )
        })
        .collect::<Vec<_>>();
    eprintln!("{:?}", hashes[0].all_prod());
    for _ in 0..Q {
        input!(qtype: usize);
        if qtype == 1 {
            input!(k: Usize1, c: char, d: char);
            for i in 0..N {
                if S[i][k] == c {
                    S[i][k] = d;
                    hashes[i].set(k, mul(POW[k], (d as u8 - b'a') as u64 + 1));
                }
            }
        } else {
            input!(t: Chars);
            let hash = (0..t.len())
                .map(|k| mul(POW[k], (t[k] as u8 - b'a' + 1) as u64))
                .fold(0, |x, y| modulo(x + y));
            let mut ans = 0;
            for i in 0..N {
                if hashes[i].prod(0, t.len()) == hash {
                    ans += 1;
                }
            }
            println!("{ans}");
        }
    }
}
// The following code was expanded by `cargo-equip`.
///  # Bundled libraries
///
///  - `ac-library-rs-parted-internal-bit 0.1.0 (path+███████████████████████████████████████████████████████████████████████████████)`              
       published in https://github.com/qryxip/ac-library-rs-parted licensed under `CC0-1.0` as `crate::__cargo_equip::crates
    ::__ac_library_rs_parted_internal_bit_0_1_0`
///  - `ac-library-rs-parted-internal-type-traits 0.1.0 (path+███████████████████████████████████████████████████████████████████████████████████████
    )` published in https://github.com/qryxip/ac-library-rs-parted licensed under `CC0-1.0` as `crate::__cargo_equip::crates
    ::__ac_library_rs_parted_internal_type_traits_0_1_0`
///  - `ac-library-rs-parted-segtree 0.1.0 (path+██████████████████████████████████████████████████████████████████████████)`                        
       published in https://github.com/qryxip/ac-library-rs-parted licensed under `CC0-1.0` as `crate::__cargo_equip::crates::acl_segtree`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod __ac_library_rs_parted_internal_bit_0_1_0 {pub use self::internal_bit::*;mod internal_bit{#[allow(dead_code)]pub fn ceil_pow2(n:u32
            )->u32{32-n.saturating_sub(1).leading_zeros()}}}
        pub mod __ac_library_rs_parted_internal_type_traits_0_1_0 {pub use self::internal_type_traits::*;mod internal_type_traits{use std::{fmt,iter
            ::{Product,Sum},ops::{Add,AddAssign,BitAnd,BitAndAssign,BitOr,BitOrAssign,BitXor,BitXorAssign,Div,DivAssign,Mul,MulAssign,Not,Rem
            ,RemAssign,Shl,ShlAssign,Shr,ShrAssign,Sub,SubAssign,},};#[doc=" Corresponds to `std::is_integral` in C++."]pub trait Integral:'static
            +Send+Sync+Copy+Ord+Not<Output=Self>+Add<Output=Self>+Sub<Output=Self>+Mul<Output=Self>+Div<Output=Self>+Rem<Output=Self>+AddAssign
            +SubAssign+MulAssign+DivAssign+RemAssign+Sum+Product+BitOr<Output=Self>+BitAnd<Output=Self>+BitXor<Output=Self>+BitOrAssign+BitAndAssign
            +BitXorAssign+Shl<Output=Self>+Shr<Output=Self>+ShlAssign+ShrAssign+fmt::Display+fmt::Debug+fmt::Binary+fmt::Octal+Zero+One+BoundedBelow
            +BoundedAbove{}#[doc=" Class that has additive identity element"]pub trait Zero{#[doc=" The additive identity element"]fn zero()->Self
            ;}#[doc=" Class that has multiplicative identity element"]pub trait One{#[doc=" The multiplicative identity element"]fn one()->Self;}pub 
            trait BoundedBelow{fn min_value()->Self;}pub trait BoundedAbove{fn max_value()->Self;}macro_rules!impl_integral{($($ty:ty),*)=>{$(impl 
            Zero for$ty{#[inline]fn zero()->Self{0}}impl One for$ty{#[inline]fn one()->Self{1}}impl BoundedBelow for$ty{#[inline]fn min_value
            ()->Self{Self::min_value()}}impl BoundedAbove for$ty{#[inline]fn max_value()->Self{Self::max_value()}}impl Integral for$ty{})*}
            ;}impl_integral!(i8,i16,i32,i64,i128,isize,u8,u16,u32,u64,u128,usize);}}
        pub mod acl_segtree {use crate::__cargo_equip::preludes::acl_segtree::*;use crate::__cargo_equip::crates
            ::__ac_library_rs_parted_internal_bit_0_1_0 as internal_bit;use crate::__cargo_equip::crates
            ::__ac_library_rs_parted_internal_type_traits_0_1_0 as internal_type_traits;pub use self::segtree::*;mod segtree{use crate::__cargo_equip
            ::preludes::acl_segtree::*;use super::internal_bit::ceil_pow2;use super::internal_type_traits::{BoundedAbove,BoundedBelow,One,Zero};use 
            std::cmp::{max,min};use std::convert::Infallible;use std::marker::PhantomData;use std::ops::{Add,Mul};pub trait Monoid{type S:Clone;fn 
            identity()->Self::S;fn binary_operation(a:&Self::S,b:&Self::S)->Self::S;}pub struct Max<S>(Infallible,PhantomData<fn()->S>);impl<S>Monoid 
            for Max<S>where S:Copy+Ord+BoundedBelow,{type S=S;fn identity()->Self::S{S::min_value()}fn binary_operation(a:&Self::S,b:&Self::S)->Self
            ::S{max(*a,*b)}}pub struct Min<S>(Infallible,PhantomData<fn()->S>);impl<S>Monoid for Min<S>where S:Copy+Ord+BoundedAbove,{type S=S;fn 
            identity()->Self::S{S::max_value()}fn binary_operation(a:&Self::S,b:&Self::S)->Self::S{min(*a,*b)}}pub struct Additive<S>(Infallible
            ,PhantomData<fn()->S>);impl<S>Monoid for Additive<S>where S:Copy+Add<Output=S>+Zero,{type S=S;fn identity()->Self::S{S::zero()}fn 
            binary_operation(a:&Self::S,b:&Self::S)->Self::S{*a+*b}}pub struct Multiplicative<S>(Infallible,PhantomData<fn()->S>);impl<S>Monoid for 
            Multiplicative<S>where S:Copy+Mul<Output=S>+One,{type S=S;fn identity()->Self::S{S::one()}fn binary_operation(a:&Self::S,b:&Self::S
            )->Self::S{*a**b}}impl<M:Monoid>Default for Segtree<M>{fn default()->Self{Segtree::new(0)}}impl<M:Monoid>Segtree<M>{pub fn new(n:usize
            )->Segtree<M>{vec![M::identity();n].into()}}impl<M:Monoid>From<Vec<M::S>>for Segtree<M>{fn from(v:Vec<M::S>)->Self{let n=v.len();let log
            =ceil_pow2(n as u32)as usize;let size=1<<log;let mut d=vec![M::identity();2*size];d[size..(size+n)].clone_from_slice(&v);let mut ret
            =Segtree{n,size,log,d};for i in(1..size).rev(){ret.update(i);}ret}}impl<M:Monoid>Segtree<M>{pub fn set(&mut self,mut p:usize,x:M::S
            ){assert!(p<self.n);p+=self.size;self.d[p]=x;for i in 1..=self.log{self.update(p>>i);}}pub fn get(&self,p:usize)->M::S{assert!(p<self.n
            );self.d[p+self.size].clone()}pub fn prod(&self,mut l:usize,mut r:usize)->M::S{assert!(l<=r&&r<=self.n);let mut sml=M::identity();let mut 
            smr=M::identity();l+=self.size;r+=self.size;while l<r{if l&1!=0{sml=M::binary_operation(&sml,&self.d[l]);l+=1;}if r&1!=0{r-=1;smr=M
            ::binary_operation(&self.d[r],&smr);}l>>=1;r>>=1;}M::binary_operation(&sml,&smr)}pub fn all_prod(&self)->M::S{self.d[1].clone()}pub fn 
            max_right<F>(&self,mut l:usize,f:F)->usize where F:Fn(&M::S)->bool,{assert!(l<=self.n);assert!(f(&M::identity()));if l==self.n{return 
            self.n;}l+=self.size;let mut sm=M::identity();while{while l%2==0{l>>=1;}if!f(&M::binary_operation(&sm,&self.d[l])){while l<self.size{l*=2
            ;let res=M::binary_operation(&sm,&self.d[l]);if f(&res){sm=res;l+=1;}}return l-self.size;}sm=M::binary_operation(&sm,&self.d[l]);l+=1
            ;{let l=l as isize;(l&-l)!=l}}{}self.n}pub fn min_left<F>(&self,mut r:usize,f:F)->usize where F:Fn(&M::S)->bool,{assert!(r<=self.n
            );assert!(f(&M::identity()));if r==0{return 0;}r+=self.size;let mut sm=M::identity();while{r-=1;while r>1&&r%2==1{r>>=1;}if!f(&M
            ::binary_operation(&self.d[r],&sm)){while r<self.size{r=2*r+1;let res=M::binary_operation(&self.d[r],&sm);if f(&res){sm=res;r-=1;}}return 
            r+1-self.size;}sm=M::binary_operation(&self.d[r],&sm);{let r=r as isize;(r&-r)!=r}}{}0}fn update(&mut self,k:usize){self.d[k]=M
            ::binary_operation(&self.d[2*k],&self.d[2*k+1]);}}pub struct Segtree<M>where M:Monoid,{n:usize,size:usize,log:usize,d:Vec<M::S>,}}}
    }
    pub(crate) mod macros {
        pub mod __ac_library_rs_parted_internal_bit_0_1_0 {}
        pub mod __ac_library_rs_parted_internal_type_traits_0_1_0 {}
        pub mod acl_segtree {}
    }
    pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}
    mod preludes {
        pub mod __ac_library_rs_parted_internal_bit_0_1_0 {}
        pub mod __ac_library_rs_parted_internal_type_traits_0_1_0 {}
        pub mod acl_segtree {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{__ac_library_rs_parted_internal_bit_0_1_0 as 
            __acl_internal_bit,__ac_library_rs_parted_internal_type_traits_0_1_0 as __acl_internal_type_traits};}
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0