結果
問題 |
No.3227 Matrix Query
|
ユーザー |
![]() |
提出日時 | 2025-08-08 22:18:24 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,176 ms / 8,000 ms |
コード長 | 1,249 bytes |
コンパイル時間 | 191 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 158,484 KB |
最終ジャッジ日時 | 2025-08-08 22:19:12 |
合計ジャッジ時間 | 36,745 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
class SegTree: def __init__(self,n,op,e): self.n=1 while self.n<n: self.n*=2 self.op=op self.e=e self.data=[e]*(2*self.n) def set(self,i,x): self.data[self.n+i]=x i+=self.n self.data[i]=x while i>1: i//=2 self.data[i]=self.op(self.data[2*i+1],self.data[2*i]) def prod(self,l,r): pl=[] pr=[] l+=self.n r+=self.n while l<r: if l%2==1: pl+=[l] l+=1 if r%2==1: r-=1 pr+=[r] l//=2 r//=2 a=self.e for i in pl+pr[::-1]: a=self.op(self.data[i],a) return a K,n=map(int,input().split()) def seki(a,b): l=2 c=[0]*l*l for i in range(l): for j in range(l): for k in range(l): c[i*l+j]+=a[i*l+k]*b[k*l+j] c[i*l+j]%=K return tuple(c) st=SegTree(n,seki,(1,0,0,1)) for i in reversed(range(n)): a=[list(map(int,input().split())) for _ in range(2)] st.set(i,tuple(a[j//2][j%2] for j in range(4))) Q=int(input()) for q in range(Q): i,l,r=map(int,input().split()) i-=1 l-=1 r-=1 i=n-1-i a=[list(map(int,input().split())) for _ in range(2)] st.set(i,tuple(a[j//2][j%2] for j in range(4))) l,r=n-1-r,n-1-l A=st.prod(l,r+1) print(*A[:2]) print(*A[2:])