結果

問題 No.3227 Matrix Query
コンテスト
ユーザー sasa8uyauya
提出日時 2025-08-08 22:10:02
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,396 bytes
コンパイル時間 214 ms
コンパイル使用メモリ 82,404 KB
実行使用メモリ 85,292 KB
最終ジャッジ日時 2025-08-08 22:10:22
合計ジャッジ時間 19,063 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 14 TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

class ST:
  def __init__(self,op,e,n):
    self.op=op
    self.e=e
    self.B=int(n**0.5)+1
    self.st1=[self.e for i in range(self.B*self.B)]
    self.st2=[self.e for i in range(self.B)]
    return
  
  def set(self,p,x):
    self.st1[p]=x
    y=p//self.B
    a=self.e
    for i in range(y*self.B,y*self.B+self.B):
      a=self.op(self.st1[i],a)
    self.st2[y]=a
    return
  
  def prod(self,l,r):
    yl=l//self.B
    yr=r//self.B
    a=self.e
    if yl==yr:
      for i in range(l,r+1):
        a=self.op(self.st1[i],a)
    else:
      for i in range(l,yl*self.B+self.B):
        a=self.op(self.st1[i],a)
      for i in range(yl+1,yr):
        a=self.op(self.st2[i],a)
      for i in range(yr*self.B,r+1):
        a=self.op(self.st1[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=ST(seki,(1,0,0,1),n)

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)
  print(*A[:2])
  print(*A[2:])
0