結果
問題 |
No.2761 Substitute and Search
|
ユーザー |
![]() |
提出日時 | 2024-05-17 21:58:31 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,350 bytes |
コンパイル時間 | 235 ms |
コンパイル使用メモリ | 82,424 KB |
実行使用メモリ | 167,736 KB |
最終ジャッジ日時 | 2024-12-20 13:45:49 |
合計ジャッジ時間 | 31,300 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 TLE * 1 |
ソースコード
class segtree: def __init__(self,n,k): self.size=1 self.m=k while self.size<n: self.size*=2 self.dat=[0]*(self.size*2) def update(self,x,a): x+=self.size self.dat[x]=a while x>1: x//=2 self.dat[x]=(self.dat[2*x]+self.dat[2*x+1])%self.m def querry(self,u,v): u+=self.size v+=self.size score=0 while u<v: if u&1: score+=self.dat[u] u+=1 if v&1: v-=1 score+=self.dat[v] u//=2 v//=2 return score%self.m mod=67280421310721 N,L,Q=map(int,input().split()) u=[1]*(L+1) for i in range(1,L+1): u[i]=u[i-1]*100 u[i]%=mod Z=[segtree(L,mod) for i in range(N)] v=[[0]*L for i in range(N)] for i in range(N): s=input() for j in range(L): x=ord(s[j])-ord('a')+1 w=x*u[j]%mod Z[i].update(j,w) v[i][j]=x for _ in range(Q): t,*A=map(str,input().split()) t=int(t) if t==1: k,c,d=A[:] k=int(k)-1 x=ord(c)-ord('a')+1 y=ord(d)-ord('a')+1 for i in range(N): if v[i][k]==x: v[i][k]=y w=y*u[k]%mod Z[i].update(k,w) else: s=A[0] e=0 for i in range(len(s)): x=ord(s[i])-ord('a')+1 e+=x*u[i]%mod e%=mod result=0 for i in range(N): b=Z[i].querry(0,len(s)) b%=mod if b==e: result+=1 print(result)