結果
| 問題 | No.1234 典型RMQ |
| ユーザー |
👑  Kazun
|
| 提出日時 | 2020-09-20 02:41:27 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,438 ms / 2,000 ms |
| コード長 | 3,395 bytes |
| コンパイル時間 | 291 ms |
| コンパイル使用メモリ | 82,560 KB |
| 実行使用メモリ | 120,224 KB |
| 最終ジャッジ日時 | 2024-04-26 11:28:38 |
| 合計ジャッジ時間 | 27,593 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 40 ms
52,736 KB |
| testcase_01 | AC | 41 ms
52,992 KB |
| testcase_02 | AC | 41 ms
53,120 KB |
| testcase_03 | AC | 41 ms
52,608 KB |
| testcase_04 | AC | 40 ms
52,992 KB |
| testcase_05 | AC | 41 ms
52,608 KB |
| testcase_06 | AC | 1,423 ms
118,612 KB |
| testcase_07 | AC | 984 ms
102,652 KB |
| testcase_08 | AC | 1,438 ms
120,224 KB |
| testcase_09 | AC | 1,307 ms
114,180 KB |
| testcase_10 | AC | 1,431 ms
119,756 KB |
| testcase_11 | AC | 1,341 ms
117,608 KB |
| testcase_12 | AC | 1,226 ms
112,096 KB |
| testcase_13 | AC | 957 ms
102,592 KB |
| testcase_14 | AC | 1,232 ms
111,960 KB |
| testcase_15 | AC | 1,161 ms
110,832 KB |
| testcase_16 | AC | 1,375 ms
119,488 KB |
| testcase_17 | AC | 1,229 ms
112,584 KB |
| testcase_18 | AC | 875 ms
95,464 KB |
| testcase_19 | AC | 1,385 ms
119,568 KB |
| testcase_20 | AC | 688 ms
101,888 KB |
| testcase_21 | AC | 1,333 ms
118,240 KB |
| testcase_22 | AC | 1,106 ms
105,984 KB |
| testcase_23 | AC | 1,042 ms
106,368 KB |
| testcase_24 | AC | 922 ms
105,984 KB |
| testcase_25 | AC | 972 ms
106,496 KB |
| testcase_26 | AC | 994 ms
106,496 KB |
| testcase_27 | AC | 41 ms
52,352 KB |
| testcase_28 | AC | 40 ms
52,736 KB |
| testcase_29 | AC | 41 ms
52,480 KB |
ソースコード
class Lazy_Evaluation_Tree():
def __init__(self,L,calc,unit,op,comp,id):
"""calcを演算,opを作用とするリストLのSegment Treeを作成
calc:演算
unit:モノイドcalcの単位元 (xe=ex=xを満たすe)
op:作用素
comp:作用素の合成
id:恒等写像
[条件] M:Monoid,F={f:F x M→ M:作用素}に対して,以下が成立する.
Fは恒等写像 id を含む.つまり,任意の x in M に対して id(x)=x
Fは写像の合成に閉じている.つまり,任意の f,g in F に対して, comp(f,g) in F
任意の f in F, x,y in M に対して,f(xy)=f(x)f(y)である.
[注記]
作用素は左から掛ける.更新も左から.
"""
self.calc=calc
self.unit=unit
self.op=op
self.comp=comp
self.id=id
N=len(L)
d=max(1,(N-1).bit_length())
k=2**d
X=[unit]*(k-1)+L+[unit]*(k-len(L))
self.num=k
self.depth=d
for i in range(k-2,-1,-1):
X[i]=calc(X[2*i+1],X[2*i+2])
self.data=X
self.lazy=[self.id]*(2*k-1)
def eval(self,k):
if self.lazy[k]==self.id: #単位元だったら終了
return
if k<self.num-1: #葉でなければ子に伝搬
self.lazy[2*k+1]=self.comp(self.lazy[k],self.lazy[2*k+1])
self.lazy[2*k+2]=self.comp(self.lazy[k],self.lazy[2*k+2])
#自身を更新(作用)
self.data[k]=self.op(self.lazy[k],self.data[k])
self.lazy[k]=self.id
return
def get(self,k,index=0):
return self.product(k,k,index)
def operate(self,From,To,alpha,index=0,left_closed=True,right_closed=True):
A=From-index+(not left_closed)
B=To-index-(not right_closed)
return self.__operate_second(A,B+1,alpha,0,0,self.num)
def __operate_second(self,a,b,alpha,k,l,r):
self.eval(k)
if (a<=l) and (r<=b): #完全に内側のとき
self.lazy[k]=self.comp(alpha,self.lazy[k])
self.eval(k)
elif (a<r) and (l<b): #一部がかぶるとき
self.__operate_second(a,b,alpha,2*k+1,l,(l+r)//2) #左の子
self.__operate_second(a,b,alpha,2*k+2,(l+r)//2,r) #右の子
self.data[k]=self.calc(self.data[2*k+1],self.data[2*k+2])
def update(self,k,x):
pass
def product(self,From,To,index=0,left_closed=True,right_closed=True):
A=From-index+(not left_closed)
B=To-index-(not right_closed)
return self.__product_second(A,B+1,0,0,self.num)
def __product_second(self,a,b,k,l,r):
self.eval(k)
if r<=a or b<=l:
return self.unit
elif a<=l and r<=b:
return self.data[k]
else:
alpha=self.__product_second(a,b,2*k+1,l,(l+r)//2)
beta=self.__product_second(a,b,2*k+2,(l+r)//2,r)
return self.calc(alpha,beta)
#================================================
N=int(input())
A=list(map(int,input().split()))
Q=int(input())
calc=lambda x,y:min(x,y)
unit=float("inf")
op=lambda a,x:a+x
comp=lambda a,b:a+b
id=0
S=Lazy_Evaluation_Tree(A,calc,unit,op,comp,id)
X=[]
for _ in range(Q):
k,l,r,c=map(int,input().split())
if k==1:
S.operate(l,r,c,1)
else:
X.append(S.product(l,r,1))
print("\n".join(map(str,X)))