結果
問題 |
No.3227 Matrix Query
|
ユーザー |
![]() |
提出日時 | 2025-08-12 04:04:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 4,578 ms / 8,000 ms |
コード長 | 1,940 bytes |
コンパイル時間 | 327 ms |
コンパイル使用メモリ | 82,656 KB |
実行使用メモリ | 264,260 KB |
最終ジャッジ日時 | 2025-08-12 04:05:44 |
合計ジャッジ時間 | 71,295 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
import sys input = sys.stdin.readline mod,N=map(int,input().split()) def prod(A,B,k,l,m):# A:k*l,B:l*m C=[[None for i in range(m)] for j in range(k)] for i in range(k): for j in range(m): ANS=0 for pl in range(l): ANS=(ANS+A[i][pl]*B[pl][j])%mod C[i][j]=ANS return C def plus(A,B,k,l):# a,B:k*l C=[[None for i in range(l)] for j in range(k)] for i in range(k): for j in range(l): C[i][j]=(A[i][j]+B[i][j])%mod return C def seg_function(x,y): # Segment treeで扱うfunction z=prod(x,y,2,2,2) return z A=[] for i in range(N): a,b=map(int,input().split()) c,d=map(int,input().split()) X=[[a,b],[c,d]] A.append(X) seg_el=1<<(N.bit_length()) # Segment treeの台の要素数 SEG=[[[1,0],[0,1]] for i in range(2*seg_el)] # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化 for i in range(N): # Aを対応する箇所へupdate SEG[i+seg_el]=A[i] for i in range(seg_el-1,0,-1): # 親の部分もupdate SEG[i]=seg_function(SEG[i*2],SEG[i*2+1]) def update(n,x,seg_el): # A[n]をxへ更新 i=n+seg_el SEG[i]=x i>>=1 # 子ノードへ while i!=0: SEG[i]=seg_function(SEG[i*2],SEG[i*2+1]) i>>=1 def getvalues(l,r): # 区間[l,r)に関するseg_functionを調べる L=l+seg_el R=r+seg_el ANS1=[[1,0],[0,1]] ANS2=[[1,0],[0,1]] while L<R: if L & 1: ANS1=seg_function(ANS1, SEG[L]) L+=1 if R & 1: R-=1 ANS2=seg_function(SEG[R], ANS2) L>>=1 R>>=1 return seg_function(ANS1, ANS2) Q=int(input()) for tests in range(Q): i,L,R=map(int,input().split()) a,b=map(int,input().split()) c,d=map(int,input().split()) update(i-1,[[a,b],[c,d]],seg_el) ANS=getvalues(L-1,R) for ans in ANS: print(*ans)