結果
問題 | No.1675 Strange Minimum Query |
ユーザー | Kazun |
提出日時 | 2021-09-10 21:42:39 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 5,468 bytes |
コンパイル時間 | 406 ms |
コンパイル使用メモリ | 82,208 KB |
実行使用メモリ | 139,448 KB |
最終ジャッジ日時 | 2024-06-11 23:06:56 |
合計ジャッジ時間 | 38,686 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 40 ms
54,652 KB |
testcase_01 | AC | 40 ms
54,464 KB |
testcase_02 | AC | 41 ms
54,048 KB |
testcase_03 | AC | 968 ms
104,992 KB |
testcase_04 | AC | 905 ms
111,540 KB |
testcase_05 | AC | 335 ms
94,792 KB |
testcase_06 | AC | 1,093 ms
109,968 KB |
testcase_07 | AC | 1,208 ms
121,012 KB |
testcase_08 | AC | 50 ms
63,212 KB |
testcase_09 | AC | 115 ms
77,168 KB |
testcase_10 | AC | 610 ms
116,340 KB |
testcase_11 | AC | 374 ms
107,472 KB |
testcase_12 | AC | 662 ms
117,660 KB |
testcase_13 | AC | 693 ms
132,352 KB |
testcase_14 | AC | 935 ms
135,344 KB |
testcase_15 | AC | 825 ms
136,860 KB |
testcase_16 | AC | 40 ms
53,828 KB |
testcase_17 | AC | 564 ms
90,252 KB |
testcase_18 | AC | 663 ms
92,176 KB |
testcase_19 | AC | 784 ms
113,240 KB |
testcase_20 | AC | 1,423 ms
123,880 KB |
testcase_21 | AC | 1,280 ms
121,204 KB |
testcase_22 | AC | 1,584 ms
127,968 KB |
testcase_23 | AC | 1,276 ms
105,620 KB |
testcase_24 | AC | 1,232 ms
108,340 KB |
testcase_25 | AC | 1,011 ms
97,300 KB |
testcase_26 | AC | 649 ms
97,152 KB |
testcase_27 | AC | 1,170 ms
119,616 KB |
testcase_28 | AC | 768 ms
113,060 KB |
testcase_29 | AC | 596 ms
110,220 KB |
testcase_30 | AC | 635 ms
96,732 KB |
testcase_31 | AC | 1,667 ms
118,704 KB |
testcase_32 | AC | 1,885 ms
137,104 KB |
testcase_33 | TLE | - |
testcase_34 | TLE | - |
testcase_35 | AC | 1,828 ms
138,916 KB |
testcase_36 | AC | 1,845 ms
139,448 KB |
ソースコード
class Lazy_Evaluation_Tree(): def __init__(self,L,calc,unit,op,comp,id,index): """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 self.index=index N=len(L) d=max(1,(N-1).bit_length()) k=1<<d self.data=[unit]*k+L+[unit]*(k-len(L)) self.lazy=[self.id]*(2*k) self.N=k self.depth=d for i in range(k-1,0,-1): self.data[i]=calc(self.data[i<<1],self.data[i<<1|1]) def _eval_at(self,m): if self.lazy[m]==self.id: return self.data[m] return self.op(self.lazy[m],self.data[m]) #配列の第m要素を下に伝搬 def _propagate_at(self,m): self.data[m]=self._eval_at(m) if m<self.N and self.lazy[m]!=self.id: self.lazy[m<<1]=self.comp( self.lazy[m], self.lazy[m<<1] ) self.lazy[m<<1|1]=self.comp( self.lazy[m], self.lazy[m<<1|1] ) self.lazy[m]=self.id #配列の第m要素より上を全て伝搬 def _propagate_above(self,m): H=m.bit_length() for h in range(H-1,0,-1): self._propagate_at(m>>h) #配列の第m要素より上を全て再計算 def _recalc_above(self,m): while m>1: m>>=1 self.data[m]=self.calc( self._eval_at(m<<1), self._eval_at(m<<1|1) ) def get(self,k): index=self.index m=k-index+self.N self._propagate_above(m) self.data[m]=self._eval_at(m) self.lazy[m]=self.id return self.data[m] #作用 def operate(self,From,To,alpha,left_closed=True,right_closed=True): index=self.index L=(From-index)+self.N+(not left_closed) R=(To-index)+self.N+(right_closed) L0=R0=-1 X,Y=L,R-1 while X<Y: if X&1: L0=max(L0,X) X+=1 if Y&1==0: R0=max(R0,Y) Y-=1 X>>=1 Y>>=1 L0=max(L0,X) R0=max(R0,Y) self._propagate_above(L0) self._propagate_above(R0) while L<R: if L&1: self.lazy[L]=self.comp(alpha,self.lazy[L]) L+=1 if R&1: R-=1 self.lazy[R]=self.comp(alpha,self.lazy[R]) L>>=1 R>>=1 self._recalc_above(L0) self._recalc_above(R0) def update(self,k,x): """ 第k要素をxに変更する. """ index=self.index m=k-index+self.N self._propagate_above(m) self.data[m]=x self.lazy[m]=self.id self._recalc_above(m) def product(self,From,To,left_closed=True,right_closed=True): index=self.index L=(From-index)+self.N+(not left_closed) R=(To-index)+self.N+(right_closed) L0=R0=-1 X,Y=L,R-1 while X<Y: if X&1: L0=max(L0,X) X+=1 if Y&1==0: R0=max(R0,Y) Y-=1 X>>=1 Y>>=1 L0=max(L0,X) R0=max(R0,Y) self._propagate_above(L0) self._propagate_above(R0) vL=vR=self.unit while L<R: if L&1: vL=self.calc(vL,self._eval_at(L)) L+=1 if R&1: R-=1 vR=self.calc(self._eval_at(R),vR) L>>=1 R>>=1 return self.calc(vL,vR) def all_product(self): return self.product(1,self.N,1) #リフレッシュ def refresh(self): for m in range(1,2*self.N): self.data[m]=self._eval_at(m) if m<self.N and self.lazy[m]!=self.id: self.lazy[m<<1]=self.comp( self.lazy[m], self.lazy[m<<1] ) self.lazy[m<<1|1]=self.comp( self.lazy[m], self.lazy[m<<1|1] ) self.lazy[m]=self.id def __getitem__(self,k): return self.get(k) def __setitem__(self,k,x): self.update(k,x) #================================================ from heapq import heapify,heappop,heappush N,Q=map(int,input().split()) P=[] for _ in range(Q): l,r,b=map(int,input().split()) P.append((l-1,r-1,b)) S=Lazy_Evaluation_Tree([1]*N,max,1,max,max,-1,0) for l,r,b in P: S.operate(l,r,b) S.refresh() X=[S[i] for i in range(N)] T=Lazy_Evaluation_Tree(X,min,10**9,min,min,-1,0) for l,r,b in P: if T.product(l,r)!=b: exit(print(-1)) print(*X)