結果
| 問題 | No.2761 Substitute and Search |
| ユーザー |
 magurofly
|
| 提出日時 | 2024-05-01 05:28:38 |
| 言語 | Rust (1.77.0) |
| 結果 |
AC
|
| 実行時間 | 1,194 ms / 4,000 ms |
| コード長 | 9,881 bytes |
| コンパイル時間 | 15,074 ms |
| コンパイル使用メモリ | 401,288 KB |
| 実行使用メモリ | 90,768 KB |
| 最終ジャッジ日時 | 2024-05-07 04:57:48 |
| 合計ジャッジ時間 | 22,026 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
6,812 KB |
| testcase_01 | AC | 1 ms
6,812 KB |
| testcase_02 | AC | 1 ms
6,812 KB |
| testcase_03 | AC | 1 ms
6,940 KB |
| testcase_04 | AC | 493 ms
90,768 KB |
| testcase_05 | AC | 1,194 ms
79,360 KB |
| testcase_06 | AC | 198 ms
79,232 KB |
| testcase_07 | AC | 774 ms
85,100 KB |
| testcase_08 | AC | 192 ms
79,232 KB |
| testcase_09 | AC | 739 ms
85,312 KB |
| testcase_10 | AC | 191 ms
79,360 KB |
| testcase_11 | AC | 713 ms
85,204 KB |
| testcase_12 | AC | 479 ms
82,148 KB |
| testcase_13 | AC | 467 ms
82,304 KB |
| testcase_14 | AC | 485 ms
82,224 KB |
| testcase_15 | AC | 471 ms
82,256 KB |
コンパイルメッセージ
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`
ソースコード
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};}
}
}