結果
| 問題 | No.2761 Substitute and Search |
| ユーザー |
 hato336
|
| 提出日時 | 2024-05-17 22:04:32 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 6,601 bytes |
| コンパイル時間 | 165 ms |
| コンパイル使用メモリ | 82,224 KB |
| 実行使用メモリ | 186,952 KB |
| 最終ジャッジ日時 | 2024-12-20 13:54:26 |
| 合計ジャッジ時間 | 6,453 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 145 ms
89,112 KB |
| testcase_01 | AC | 143 ms
89,048 KB |
| testcase_02 | AC | 151 ms
89,324 KB |
| testcase_03 | AC | 145 ms
89,020 KB |
| testcase_04 | RE | - |
| testcase_05 | RE | - |
| testcase_06 | RE | - |
| testcase_07 | RE | - |
| testcase_08 | RE | - |
| testcase_09 | RE | - |
| testcase_10 | RE | - |
| testcase_11 | RE | - |
| testcase_12 | RE | - |
| testcase_13 | RE | - |
| testcase_14 | RE | - |
| testcase_15 | RE | - |
ソースコード
import collections,sys,math,functools,operator,itertools,bisect,heapq,decimal,string,time,random
#sys.setrecursionlimit(10**9)
#https://github.com/shakayami/ACL-for-python/blob/master/lazysegtree.py
class lazy_segtree():
def update(self,k):self.d[k]=self.op(self.d[2*k],self.d[2*k+1])
def all_apply(self,k,f):
self.d[k]=self.mapping(f,self.d[k])
if (k<self.size):self.lz[k]=self.composition(f,self.lz[k])
def push(self,k):
self.all_apply(2*k,self.lz[k])
self.all_apply(2*k+1,self.lz[k])
self.lz[k]=self.identity
def __init__(self,V,OP,E,MAPPING,COMPOSITION,ID):
self.n=len(V)
self.log=(self.n-1).bit_length()
self.size=1<<self.log
self.d=[E for i in range(2*self.size)]
self.lz=[ID for i in range(self.size)]
self.e=E
self.op=OP
self.mapping=MAPPING
self.composition=COMPOSITION
self.identity=ID
for i in range(self.n):self.d[self.size+i]=V[i]
for i in range(self.size-1,0,-1):self.update(i)
def set(self,p,x):
assert 0<=p and p<self.n
p+=self.size
for i in range(self.log,0,-1):self.push(p>>i)
self.d[p]=x
for i in range(1,self.log+1):self.update(p>>i)
def get(self,p):
assert 0<=p and p<self.n
p+=self.size
for i in range(self.log,0,-1):self.push(p>>i)
return self.d[p]
def prod(self,l,r):
assert 0<=l and l<=r and r<=self.n
if l==r:return self.e
l+=self.size
r+=self.size
for i in range(self.log,0,-1):
if (((l>>i)<<i)!=l):self.push(l>>i)
if (((r>>i)<<i)!=r):self.push(r>>i)
sml,smr=self.e,self.e
while(l<r):
if l&1:
sml=self.op(sml,self.d[l])
l+=1
if r&1:
r-=1
smr=self.op(self.d[r],smr)
l>>=1
r>>=1
return self.op(sml,smr)
def all_prod(self):return self.d[1]
def apply_point(self,p,f):
assert 0<=p and p<self.n
p+=self.size
for i in range(self.log,0,-1):self.push(p>>i)
self.d[p]=self.mapping(f,self.d[p])
for i in range(1,self.log+1):self.update(p>>i)
def apply(self,l,r,f):
assert 0<=l and l<=r and r<=self.n
if l==r:return
l+=self.size
r+=self.size
for i in range(self.log,0,-1):
if (((l>>i)<<i)!=l):self.push(l>>i)
if (((r>>i)<<i)!=r):self.push((r-1)>>i)
l2,r2=l,r
while(l<r):
if (l&1):
self.all_apply(l,f)
l+=1
if (r&1):
r-=1
self.all_apply(r,f)
l>>=1
r>>=1
l,r=l2,r2
for i in range(1,self.log+1):
if (((l>>i)<<i)!=l):self.update(l>>i)
if (((r>>i)<<i)!=r):self.update((r-1)>>i)
def max_right(self,l,g):
assert 0<=l and l<=self.n
assert g(self.e)
if l==self.n:return self.n
l+=self.size
for i in range(self.log,0,-1):self.push(l>>i)
sm=self.e
while(1):
while(l%2==0):l>>=1
if not(g(self.op(sm,self.d[l]))):
while(l<self.size):
self.push(l)
l=(2*l)
if (g(self.op(sm,self.d[l]))):
sm=self.op(sm,self.d[l])
l+=1
return l-self.size
sm=self.op(sm,self.d[l])
l+=1
if (l&-l)==l:break
return self.n
def min_left(self,r,g):
assert (0<=r and r<=self.n)
assert g(self.e)
if r==0:return 0
r+=self.size
for i in range(self.log,0,-1):self.push((r-1)>>i)
sm=self.e
while(1):
r-=1
while(r>1 and (r%2)):r>>=1
if not(g(self.op(self.d[r],sm))):
while(r<self.size):
self.push(r)
r=(2*r+1)
if g(self.op(self.d[r],sm)):
sm=self.op(self.d[r],sm)
r-=1
return r+1-self.size
sm=self.op(self.d[r],sm)
if (r&-r)==r:break
return 0
mod = 998244353
#区間加算・区間最小値取得 lst = lazy_segtree([],min,10**18,operator.add,operator.add,0)
#区間加算・区間最大値取得 lst = lazy_segtree([],max,-10**18,operator.add,operator.add,0)
#区間加算・区間和取得 lst = lazy_segtree([(alist[i],1) for i in range(n)],lambda x,y:((x[0]+y[0])%mod,x[1]+y[1]),(0,0),lambda x,y:((y[0]+x*y[1])%mod,y[1]),operator.add,0)
#区間変更・区間最小値取得 lst = lazy_segtree([],min,10**18,lambda x,y:y if x == 10**18 else x,lambda x,y:y if x == 10**18 else x,10**18)
#区間変更・区間最大値取得 lst = lazy_segtree([],max,-10**18,lambda x,y:y if x == -10**18 else x,lambda x,y:y if x == -10**18 else x,-10**18)
#区間変更・区間和取得 lst = lazy_segtree([(alist[i],1) for i in range(n)],lambda x,y:((x[0]+y[0])%mod,x[1]+y[1]),(0,0),lambda x,y:(y[1]*x,y[1]) if x != 10**18 else y,lambda x,y:y if x == 10**18 else x,10**18)
def op(x,y):
return
#xはlazy, yはd
def mapping(x,y):
return
#yが作用してからxが作用する
def composition(x,y):
return
#sys.set_int_max_str_digits(0)
input = sys.stdin.readline
#n = int(input())
#
mod = 2**61-1
#alist = []
#s = input()
n,l,q = map(int,input().split())
lst = [lazy_segtree([0 for i in range(l)],min,10**18,lambda x,y:(x+y)%mod,lambda x,y:(x+y)%mod,0) for fjdfb in range(n)]
base = random.randint(100,10000)
s = []
base_pow = [pow(base,i,mod) for i in range(1000+10)]
for i in range(n):
t = list(input().rstrip())
s.append(t)
temp = 0
for j in range(l):
temp += (ord(t[j]) - ord('a')) * base_pow[j]
temp %= mod
lst[i].set(j,temp)
for _ in range(q):
query = list(input().split())
if query[0] == '1':
t,k,c,d = query
k = int(k)
k -= 1
for i in range(n):
if s[i][k] == c:
lst[i].apply(k,l,-((ord(c) - ord('a')) * base_pow[k]))
lst[i].apply(k,l,(ord(d) - ord('a')) * base_pow[k])
s[i][k] = d
else:
e,t = query
t = t.rstrip()
t = list(t)
ans = 0
temp = 0
for i in range(len(t)):
temp += (ord(t[i]) - ord('a')) * base_pow[i]
temp %= mod
for i in range(n):
if lst[i].get(len(t)-1) == temp:
ans += 1
print(ans)