結果
問題 | No.1234 典型RMQ |
ユーザー | chineristAC |
提出日時 | 2020-09-18 21:47:04 |
言語 | PyPy3 (7.3.13) |
結果 |
AC
|
実行時間 | 419 ms / 2,000 ms |
コード長 | 2,795 bytes |
コンパイル時間 | 1,554 ms |
コンパイル使用メモリ | 86,756 KB |
実行使用メモリ | 95,460 KB |
最終ジャッジ日時 | 2023-08-08 18:36:58 |
合計ジャッジ時間 | 11,979 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 68 ms
71,152 KB |
testcase_01 | AC | 63 ms
71,328 KB |
testcase_02 | AC | 67 ms
71,052 KB |
testcase_03 | AC | 64 ms
71,288 KB |
testcase_04 | AC | 64 ms
71,188 KB |
testcase_05 | AC | 65 ms
71,328 KB |
testcase_06 | AC | 400 ms
90,440 KB |
testcase_07 | AC | 362 ms
81,712 KB |
testcase_08 | AC | 413 ms
94,692 KB |
testcase_09 | AC | 376 ms
84,932 KB |
testcase_10 | AC | 396 ms
92,964 KB |
testcase_11 | AC | 398 ms
90,196 KB |
testcase_12 | AC | 389 ms
84,380 KB |
testcase_13 | AC | 363 ms
82,104 KB |
testcase_14 | AC | 393 ms
84,152 KB |
testcase_15 | AC | 391 ms
83,492 KB |
testcase_16 | AC | 419 ms
93,224 KB |
testcase_17 | AC | 385 ms
84,276 KB |
testcase_18 | AC | 336 ms
80,664 KB |
testcase_19 | AC | 415 ms
94,736 KB |
testcase_20 | AC | 248 ms
94,428 KB |
testcase_21 | AC | 396 ms
90,460 KB |
testcase_22 | AC | 363 ms
95,248 KB |
testcase_23 | AC | 375 ms
95,116 KB |
testcase_24 | AC | 362 ms
95,140 KB |
testcase_25 | AC | 357 ms
95,072 KB |
testcase_26 | AC | 364 ms
95,460 KB |
testcase_27 | AC | 66 ms
71,084 KB |
testcase_28 | AC | 64 ms
71,052 KB |
testcase_29 | AC | 62 ms
71,348 KB |
ソースコード
class LazySegmentTree(): __slots__ = ["merge","merge_unit","operate","merge_operate","operate_unit","n","data","lazy"] def __init__(self,n,init,merge,merge_unit,operate,merge_operate,operate_unit): self.merge=merge self.merge_unit=merge_unit self.operate=operate self.merge_operate=merge_operate self.operate_unit=operate_unit self.n=(n-1).bit_length() self.data=[merge_unit for i in range(1<<(self.n+1))] self.lazy=[operate_unit for i in range(1<<(self.n+1))] if init: for i in range(n): self.data[2**self.n+i]=init[i] for i in range(2**self.n-1,0,-1): self.data[i]=self.merge(self.data[2*i],self.data[2*i+1]) def propagate(self,v): ope = self.lazy[v] if ope == self.operate_unit: return self.lazy[v]=self.operate_unit self.data[(v<<1)]=self.operate(self.data[(v<<1)],ope) self.data[(v<<1)+1]=self.operate(self.data[(v<<1)+1],ope) self.lazy[v<<1]=self.merge_operate(self.lazy[(v<<1)],ope) self.lazy[(v<<1)+1]=self.merge_operate(self.lazy[(v<<1)+1],ope) def propagate_above(self,i): m=i.bit_length()-1 for bit in range(m,0,-1): v=i>>bit self.propagate(v) def remerge_above(self,i): while i: c = self.merge(self.data[i],self.data[i^1]) i>>=1 self.data[i]=self.operate(c,self.lazy[i]) def update(self,l,r,x): l+=1<<self.n r+=1<<self.n l0=l//(l&-l) r0=r//(r&-r)-1 while l<r: if l&1: self.data[l]=self.operate(self.data[l],x) self.lazy[l]=self.merge_operate(self.lazy[l],x) l+=1 if r&1: self.data[r-1]=self.operate(self.data[r-1],x) self.lazy[r-1]=self.merge_operate(self.lazy[r-1],x) l>>=1 r>>=1 self.remerge_above(l0) self.remerge_above(r0) def query(self,l,r): l+=1<<self.n r+=1<<self.n l0=l//(l&-l) r0=r//(r&-r)-1 self.propagate_above(l0) self.propagate_above(r0) res=self.merge_unit while l<r: if l&1: res=self.merge(res,self.data[l]) l+=1 if r&1: res=self.merge(res,self.data[r-1]) l>>=1 r>>=1 return res import sys input = sys.stdin.readline N = int(input()) a = list(map(int,input().split())) LST = LazySegmentTree(N,a,min,10**18,lambda x,y:x+y,lambda x,y:x+y,0) for _ in range(int(input())): k,l,r,c = map(int,input().split()) l-=1 if k==1: LST.update(l,r,c) else: print(LST.query(l,r))