結果
問題 | No.1675 Strange Minimum Query |
ユーザー |
👑 ![]() |
提出日時 | 2021-09-10 21:47:15 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 9,967 bytes |
コンパイル時間 | 418 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 133,308 KB |
最終ジャッジ日時 | 2024-06-11 23:21:06 |
合計ジャッジ時間 | 29,112 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 16 WA * 18 |
ソースコード
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)=xFは写像の合成に閉じている.つまり,任意の f,g in F に対して, comp(f,g) in F任意の f in F, x,y in M に対して,f(xy)=f(x)f(y)である.[注記]作用素は左から掛ける.更新も左から."""self.calc=calcself.unit=unitself.op=opself.comp=compself.id=idself.index=indexN=len(L)d=max(1,(N-1).bit_length())k=1<<dself.data=[unit]*k+L+[unit]*(k-len(L))self.lazy=[self.id]*(2*k)self.N=kself.depth=dfor 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>>=1self.data[m]=self.calc(self._eval_at(m<<1),self._eval_at(m<<1|1))def get(self,k):index=self.indexm=k-index+self.Nself._propagate_above(m)self.data[m]=self._eval_at(m)self.lazy[m]=self.idreturn self.data[m]#作用def operate(self,From,To,alpha,left_closed=True,right_closed=True):index=self.indexL=(From-index)+self.N+(not left_closed)R=(To-index)+self.N+(right_closed)L0=R0=-1X,Y=L,R-1while X<Y:if X&1:L0=max(L0,X)X+=1if Y&1==0:R0=max(R0,Y)Y-=1X>>=1Y>>=1L0=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+=1if R&1:R-=1self.lazy[R]=self.comp(alpha,self.lazy[R])L>>=1R>>=1self._recalc_above(L0)self._recalc_above(R0)def update(self,k,x):""" 第k要素をxに変更する."""index=self.indexm=k-index+self.Nself._propagate_above(m)self.data[m]=xself.lazy[m]=self.idself._recalc_above(m)def product(self,From,To,left_closed=True,right_closed=True):index=self.indexL=(From-index)+self.N+(not left_closed)R=(To-index)+self.N+(right_closed)L0=R0=-1X,Y=L,R-1while X<Y:if X&1:L0=max(L0,X)X+=1if Y&1==0:R0=max(R0,Y)Y-=1X>>=1Y>>=1L0=max(L0,X)R0=max(R0,Y)self._propagate_above(L0)self._propagate_above(R0)vL=vR=self.unitwhile L<R:if L&1:vL=self.calc(vL,self._eval_at(L))L+=1if R&1:R-=1vR=self.calc(self._eval_at(R),vR)L>>=1R>>=1return 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.iddef __getitem__(self,k):return self.get(k)def __setitem__(self,k,x):self.update(k,x)class Segment_Tree():"""このプログラム内は1-index"""def __init__(self,L,calc,unit,index):"""calcを演算とするリストLのSegment Treeを作成calc:演算(2変数関数,モノイド)unit:モノイドcalcの単位元 (xe=ex=xを満たすe)index:数列の第1要素のindex"""self.calc=calcself.unit=unitself.index=indexN=len(L)d=max(1,(N-1).bit_length())k=1<<dself.data=[unit]*k+L+[unit]*(k-len(L))self.N=kself.depth=dfor i in range(k-1,0,-1):self.data[i]=self.calc(self.data[i<<1],self.data[i<<1|1])def get(self,k,index=1):"""第k要素を取得"""assert 0<=k-index<self.N,"添字が範囲外"return self.data[k-index+self.N]def update(self,k,x,index=1):"""第k要素をxに変え,更新を行う.k:数列の要素x:更新後の値"""assert 0<=k-index<self.N,"添字が範囲外"m=(k-index)+self.Nself.data[m]=xwhile m>1:m>>=1self.data[m]=self.calc(self.data[m<<1],self.data[m<<1|1])def product(self,From,To,index=1,left_closed=True,right_closed=True):L=(From-index)+self.N+(not left_closed)R=(To-index)+self.N+(right_closed)vL=self.unitvR=self.unitwhile L<R:if L&1:vL=self.calc(vL,self.data[L])L+=1if R&1:R-=1vR=self.calc(self.data[R],vR)L>>=1R>>=1return self.calc(vL,vR)def all_product(self):return self.data[1]def max_right(self,left,cond,index=1):"""以下の2つをともに満たすxの1つを返す.\n(1) x=left or cond(data[left]*data[left+1]*...*data[x-1]):True(2) x=N+index or cond(data[left]*data[left+1]*...*data[x]):False※condが単調減少の時,cond(data[left]*...*data[x-1])を満たす最大のxとなる.cond:関数(引数が同じならば結果も同じ)cond(unit):Trueindex<=left<=r<n+index"""left-=indexassert 0<=left<=self.N,"添字が範囲外"assert cond(self.unit),"単位元が条件を満たさない."if left==self.N:return self.N+indexleft+=self.N-(index-1)sm=self.unitcalc=self.calcfirst=Truewhile first or (left & (-left))!=left:first=Falsewhile left%2==0:left>>=1if not cond(calc(sm,self.data[left])):while left<self.N:left<<=1if cond(self.calc(sm,self.data[left])):sm=self.calc(sm,self.data[left])left+=1return left-self.N+indexsm=self.calc(sm,self.data[left])left+=1return self.N+indexdef min_left(self,right,cond,index=1):"""以下の2つをともに満たすyの1つを返す.\n(1) y=right or cond(data[y]*data[y+1]*...*data[right]):True(2) y=index or cond(data[y-1]*data[y]*...*data[right]):False※condが単調減少の時,cond(data[y]*...*data[right-1])を満たす最大のyとなる.cond:関数(引数が同じならば結果も同じ)cond(unit):Trueindex<=left<=r<n+index"""right-=indexassert 0<=right<=self.N,"添字が範囲外"assert cond(self.unit),"単位元が条件を満たさない."if right==0:return indexright+=self.Nsm=self.unitcalc=self.calcfirst=1while first or (right & (-right))!=right:first=0right-=1while right>1 and right&1:right>>=1if not cond(calc(self.data[right],sm)):while right<self.N:right=2*right+1if cond(calc(self.data[right],sm)):sm=calc(self.data[right],sm)right-=1return right+1-self.N+indexsm=calc(self.data[right],sm)return indexdef __getitem__(self,k):return self.get(k,self.index)def __setitem__(self,k,x):return self.update(k,x,self.index)#================================================import sysfrom heapq import heapify,heappop,heappushinput=sys.stdin.readlineN,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=Segment_Tree(X,min,10**9,0)for l,r,b in P:if T.product(l+1,r)!=b:exit(print(-1))print(*X)