結果
問題 | No.2761 Substitute and Search |
ユーザー |
|
提出日時 | 2024-05-17 21:42:06 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 310 ms / 4,000 ms |
コード長 | 1,000 bytes |
コンパイル時間 | 1,096 ms |
コンパイル使用メモリ | 90,748 KB |
実行使用メモリ | 18,304 KB |
最終ジャッジ日時 | 2024-12-20 13:27:57 |
合計ジャッジ時間 | 4,990 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 |
ソースコード
#include<iostream> #include<random> #include<cassert> #include<atcoder/fenwicktree> #include<atcoder/modint> using namespace std; using mint=atcoder::static_modint<1000000901>; mint pB[3000]; int N,L,Q; string S[1000]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); { random_device seed; mt19937 rng(seed()); mint B=rng()%(mint::mod()-1)+1; pB[0]=1; for(int i=1;i<3000;i++)pB[i]=pB[i-1]*B; } cin>>N>>L>>Q; vector<atcoder::fenwick_tree<mint> >H(N); for(int i=0;i<N;i++) { cin>>S[i]; H[i]=atcoder::fenwick_tree<mint>(L); for(int j=0;j<L;j++)H[i].add(j,S[i][j]*pB[j]); } for(int i=0;i<Q;i++) { int op;cin>>op; if(op==1) { int k;char c,d; cin>>k>>c>>d;k--; for(int i=0;i<N;i++)if(S[i][k]==c) { S[i][k]=d; H[i].add(k,((int)d-(int)c)*pB[k]); } } else { string t;cin>>t; mint h=0; for(int j=0;j<t.size();j++)h+=t[j]*pB[j]; int cnt=0; for(int i=0;i<N;i++)if(H[i].sum(0,t.size())==h)cnt++; cout<<cnt<<"\n"; } } }