結果

問題 No.3227 Matrix Query
コンテスト
ユーザー sasa8uyauya
提出日時 2025-08-08 22:06:04
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,321 bytes
コンパイル時間 242 ms
コンパイル使用メモリ 82,552 KB
実行使用メモリ 131,636 KB
最終ジャッジ日時 2025-08-08 22:06:59
合計ジャッジ時間 17,563 ms
ジャッジサーバーID
（参考情報） 		judge5 / 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 for i in range(l)]
  for i in range(l):
    for j in range(l):
      for k in range(l):
        c[i][j]+=a[i][k]*b[k][j]
        c[i][j]%=K
  return c

st=ST(seki,[[1,0],[0,1]],n)

for i in reversed(range(n)):
  st.set(i,[list(map(int,input().split())) for _ in range(2)])

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
  st.set(i,[list(map(int,input().split())) for _ in range(2)])
  l,r=n-1-r,n-1-l
  A=st.prod(l,r)
  print(*A[0])
  print(*A[1])
0