結果
問題 | No.2395 区間二次変換一点取得 |
ユーザー |
![]() |
提出日時 | 2023-07-30 02:42:49 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 1,267 ms / 2,000 ms |
コード長 | 944 bytes |
コンパイル時間 | 247 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 36,480 KB |
最終ジャッジ日時 | 2024-10-08 15:48:30 |
合計ジャッジ時間 | 12,683 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
import sysinput = sys.stdin.readlineN,B,Q=map(int,input().split())seg_el=1<<((N+1).bit_length()) # Segment treeの台の要素数SEG=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化def getvalue(n,seg_el): # 一点の値を取得i=n+seg_elANS=SEG[i]i>>=1# 子ノードへwhile i!=0:ANS+=SEG[i]i>>=1return ANSdef updates(l,r):L=l+seg_elR=r+seg_elwhile L<R:if L & 1:SEG[L]+=1L+=1if R & 1:R-=1SEG[R]+=1L>>=1R>>=1ANS=[0]*Qfor tests in range(Q):L,M,R=map(int,input().split())updates(L,R+1)ANS[tests]=getvalue(M,seg_el)LANS=[[1,1,1] for i in range(Q+1)]for i in range(Q):a,b,c=LANS[i]na=(a+1)%Bnb=(3*b+2*na*c)%Bnc=3*c%BLANS[i+1]=[na,nb,nc]for i in range(Q):print(*LANS[ANS[i]])