結果
問題 | No.2761 Substitute and Search |
ユーザー | ゼット |
提出日時 | 2024-05-17 21:58:31 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 3,898 ms / 4,000 ms |
コード長 | 1,350 bytes |
コンパイル時間 | 587 ms |
コンパイル使用メモリ | 83,040 KB |
実行使用メモリ | 167,980 KB |
最終ジャッジ日時 | 2024-05-17 21:59:14 |
合計ジャッジ時間 | 27,396 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 35 ms
52,952 KB |
testcase_01 | AC | 36 ms
52,892 KB |
testcase_02 | AC | 34 ms
53,672 KB |
testcase_03 | AC | 33 ms
52,740 KB |
testcase_04 | AC | 2,278 ms
167,456 KB |
testcase_05 | AC | 3,898 ms
166,248 KB |
testcase_06 | AC | 1,259 ms
165,796 KB |
testcase_07 | AC | 2,566 ms
167,152 KB |
testcase_08 | AC | 1,373 ms
166,252 KB |
testcase_09 | AC | 2,551 ms
167,180 KB |
testcase_10 | AC | 1,233 ms
165,800 KB |
testcase_11 | AC | 2,511 ms
167,980 KB |
testcase_12 | AC | 1,980 ms
167,124 KB |
testcase_13 | AC | 1,890 ms
167,380 KB |
testcase_14 | AC | 1,927 ms
166,372 KB |
testcase_15 | AC | 1,954 ms
166,704 KB |
ソースコード
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)