結果

問題 No.3227 Matrix Query
コンテスト
ユーザー sasa8uyauya
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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:])
0