結果
問題 | No.1675 Strange Minimum Query |
ユーザー |
![]() |
提出日時 | 2024-09-28 15:58:14 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 25,610 bytes |
コンパイル時間 | 276 ms |
コンパイル使用メモリ | 82,388 KB |
実行使用メモリ | 140,036 KB |
最終ジャッジ日時 | 2024-09-28 15:58:39 |
合計ジャッジ時間 | 22,581 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 WA * 12 |
ソースコード
from collections import defaultdictclass Segment_Tree:def __init__(self,N,f,e,lst=None,dynamic=False,bisect_search=True):self.f=fself.e=eself.N=Nself.bisect_search=bisect_searchif self.bisect_search:self.le=1while self.le<self.N:self.le*=2else:self.le=self.Nif dynamic:self.segment_tree=defaultdict(lambda:self.e)else:if lst==None:self.segment_tree=[self.e]*2*self.leelse:assert len(lst)<=self.Nself.segment_tree=[self.e]*self.le+[x for x in lst]+[self.e]*(self.le-len(lst))for i in range(self.le-1,0,-1):self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])def __getitem__(self,i):if type(i)==int:if -self.le<=i<0:return self.segment_tree[i+self.le*2]elif 0<=i<self.le:return self.segment_tree[i+self.le]else:raise IndexError("list index out of range")else:a,b,c=i.start,i.stop,i.stepif a==None:a=self.leelse:a+=self.leif b==None:b=self.le*2else:b+=self.lereturn self.segment_tree[slice(a,b,c)]def __setitem__(self,i,x):if -self.le<=i<0:i+=self.le*2elif 0<=i<self.le:i+=self.leelse:raise IndexError("list index out of range")self.segment_tree[i]=xwhile i>1:i>>= 1self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])def Build(self,lst):for i,x in enumerate(lst,self.le):self.segment_tree[i]=xfor i in range(self.le-1,0,-1):self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])def Fold(self,L=None,R=None):if L==None:L=self.leelse:assert 0<=L<=self.NL+=self.leif R==None:R=self.le*2else:assert 0<=R<=self.NR+=self.levL=self.evR=self.ewhile L<R:if L&1:vL=self.f(vL,self.segment_tree[L])L+=1if R&1:R-=1vR=self.f(self.segment_tree[R],vR)L>>=1R>>=1return self.f(vL,vR)def Fold_Index(self,L=None,R=None):if L==None:L=self.leelse:assert 0<=L<=self.NL+=self.leif R==None:R=self.le*2else:assert 0<=R<=self.NR+=self.leif L==R:return Nonex=self.Fold(L-self.le,R-self.le)while L<R:if L&1:if self.segment_tree[L]==x:i=LbreakL+=1if R&1:R-=1if self.segment_tree[R]==x:i=RbreakL>>=1R>>=1while i<self.le:if self.segment_tree[i]==self.segment_tree[i<<1]:i<<=1else:i<<=1i|=1i-=self.lereturn idef Bisect_Right(self,L=None,f=None):assert self.bisect_searchif L==self.le:return self.leif L==None:L=0assert 0<=L<=self.NL+=self.levl=self.evr=self.el,r=L,self.le*2while l<r:if l&1:vl=self.f(vl,self.segment_tree[l])l+=1if r&1:r-=1vr=self.f(self.segment_tree[r],vr)l>>=1r>>=1if f(self.f(vl,vr)):return self.Nv=self.ewhile True:while L%2==0:L>>=1vv=self.f(v,self.segment_tree[L])if f(vv):v=vvL+=1else:while L<self.le:L<<=1vv=self.f(v,self.segment_tree[L])if f(vv):v=vvL+=1return L-self.ledef Bisect_Left(self,R=None,f=None):assert self.bisect_searchif R==0:return 0if R==None:R=self.leassert 0<=R<=self.NR+=self.levl=self.evr=self.el,r=self.le,Rwhile l<r:if l&1:vl=self.f(vl,self.segment_tree[l])l+=1if r&1:r-=1vr=self.f(self.segment_tree[r],vr)l>>=1r>>=1if f(self.f(vl,vr)):return 0v=self.ewhile True:R-=1while R>1 and R%2:R>>=1vv=self.f(self.segment_tree[R],v)if f(vv):v=vvelse:while R<self.le:R=2*R+1vv=self.f(self.segment_tree[R],v)if f(vv):v=vvR-=1return R+1-self.ledef __str__(self):return "["+", ".join(map(str,[self.segment_tree[i] for i in range(self.le,self.le+self.N)]))+"]"def __repr__(self):return "Segment_Tree("+str(self)+")"class Segment_Tree_2d:def __init__(self,N,M,f,e,lst=None,dynamic=False):self.N=Nself.M=Mself.f=fself.e=eif dynamic:self.segment_tree=defaultdict(lambda:defaultdict(lambda:e))else:if lst==None:self.segment_tree=[[self.e]*2*self.M for i in range(2*self.N)]else:assert len(lst)<=self.Nassert all(len(lst[i])<=self.M for i in range(self.N))self.segment_tree=[[self.e]*2*self.M for i in range(self.N)]+[[self.e]*self.M+lst[i]+[self.e]*(self.M-len(lst[i])) for i in range(len(lst))]+[[self.e]*2*self.M for i in range(self.N-len(lst))]for i in range(self.N-1,0,-1):for j in range(2*self.M-1,self.M-1,-1):self.segment_tree[i][j]=self.f(self.segment_tree[i<<1][j],self.segment_tree[i<<1|1][j])for i in range(2*self.N-1,-1,-1):for j in range(self.M-1,0,-1):self.segment_tree[i][j]=self.f(self.segment_tree[i][j<<1],self.segment_tree[i][j<<1|1])def __getitem__(self,tpl):i,j=tpli+=self.Nj+=self.Mreturn self.segment_tree[i][j]def __setitem__(self,tpl,x):i,j=tpli+=self.Nj+=self.Mself.segment_tree[i][j]=xidxN=[i]idxM=[j]while i>1:i>>=1idxN.append(i)while j>1:j>>=1idxM.append(j)i=idxN[0]for j in idxM[1:]:self.segment_tree[i][j]=self.f(self.segment_tree[i][j<<1],self.segment_tree[i][j<<1|1])for i in idxN[1:]:for j in idxM:self.segment_tree[i][j]=self.f(self.segment_tree[i<<1][j],self.segment_tree[i<<1|1][j])def Build(self,lst):assert len(lst)<=self.Nassert all(len(lst[i] for i in range(self.N))<=self.M)for i in range(len(lst)):for j in range(len(lst[i])):self.segment_tree[i+self.N][j+self.M]=lst[i][j]for i in range(self.N-1,0,-1):for j in range(2*self.M-1,self.M-1,-1):self.segment_tree[i][j]=self.f(self.segment_tree[i<<1][j],self.segment_tree[i<<1|1][j])for i in range(2*self.N-1,-1,-1):for j in range(self.M-1,0,-1):self.segment_tree[i][j]=self.f(self.segment_tree[i][j<<1],self.segment_tree[i][j<<1|1])def Fold(self,LN=None,RN=None,LM=None,RM=None):LN+=self.NRN+=self.NLM+=self.MRM+=self.MidxN=[]idxM=[]while LN<RN:if LN&1:idxN.append(LN)LN+=1if RN&1:RN-=1idxN.append(RN)LN>>=1RN>>=1while LM<RM:if LM&1:idxM.append(LM)LM+=1if RM&1:RM-=1idxM.append(RM)LM>>=1RM>>=1retu=self.efor i in idxN:for j in idxM:retu=self.f(retu,self.segment_tree[i][j])return retudef Fold_Index(self,LN=None,RN=None,LM=None,RM=None):if LN==None:LN=self.Nelse:LN+=self.Nif RN==None:RN=self.N*2else:RN+=self.Nif LM==None:LM=self.Melse:LM+=self.Mif RM==None:RM=self.M*2else:RM+=self.Mif LN==RN and LM==RM:return NoneidxN=[]idxM=[]while LN<RN:if LN&1:idxN.append(LN)LN+=1if RN&1:RN-=1idxN.append(RN)LN>>=1RN>>=1while LM<RM:if LM&1:idxM.append(LM)LM+=1if RM&1:RM-=1idxM.append(RM)LM>>=1RM>>=1v=self.efor i in idxN:for j in idxM:v=self.f(v,self.segment_tree[i][j])for i in idxN:for j in idxM:if v==self.f(v,self.segment_tree[i][j]):breakelse:continuebreakwhile i<self.N:if self.segment_tree[i<<1][j]==v:i<<=1else:i<<=1i|=1while j<self.M:if self.segment_tree[i][j<<1]==v:j<<=1else:j<<=1j|=1return i,jdef __str__(self):m=max(len(str(self.segment_tree[i][j])) for i in range(self.N,self.N*2) for j in range(self.M,self.M*2))return "\n".join(["["+", ".join(map(lambda s:" "*(m-len(str(s)))+str(s),self.segment_tree[i][self.M:]))+"]" for i in range(self.N,self.N*2)])def __repr__(self):return "Segment_Tree_2d(\n"+str(self)+")"class Dual_Segment_Tree:def __init__(self,N,f_act,e_act,operate,lst):self.N=Nself.f_act=f_actself.e_act=e_actself.operate=operateself.lst=[None]*self.Nfor i,x in enumerate(lst):self.lst[i]=xself.segment_tree_act=[self.e_act]*(self.N+self.N)def __getitem__(self,i):if type(i) is int:if -self.N<=i<0:i+=self.N*2elif 0<=i<self.N:i+=self.Nelse:raise IndexError("list index out of range")self.Propagate_Above(i)return self.Operate_At(i)else:a,b,c=i.start,i.stop,i.stepif a==None or a<-self.N:a=0elif self.N<=a:a=self.Nelif a<0:a+=self.Nif b==None or self.N<=b:b=self.Nelif b<-self.N:b=0elif b<0:b+=self.Nreturn self.lst[slice(a,b,c)]def Operate_At(self,i):return self.operate(self.lst[i-self.N],self.segment_tree_act[i])def Propagate_At(self,i):self.segment_tree_act[i<<1]=self.f_act(self.segment_tree_act[i<<1],self.segment_tree_act[i])self.segment_tree_act[i<<1|1]=self.f_act(self.segment_tree_act[i<<1|1],self.segment_tree_act[i])self.segment_tree_act[i]=self.e_actdef Propagate_Above(self,i):H=i.bit_length()-1for h in range(H,0,-1):self.Propagate_At(i>>h)def Operate_Range(self,a,L=None,R=None):if L==None:L=self.Nelse:L+=self.Nif R==None:R=self.N*2else:R+=self.NL0=L//(L&-L)R0=R//(R&-R)-1self.Propagate_Above(L0)self.Propagate_Above(R0)while L<R:if L&1:self.segment_tree_act[L]=self.f_act(self.segment_tree_act[L],a)L+=1if R&1:R-=1self.segment_tree_act[R]=self.f_act(self.segment_tree_act[R],a)L>>=1R>>=1def Update(self):for i in range(1,self.N):self.Propagate_At(i)self.segment_tree_act[i]=self.e_actdef __str__(self):import copysegment_tree_act=copy.deepcopy(self.segment_tree_act)for i in range(1,self.N):segment_tree_act[i<<1]=self.f_act(segment_tree_act[i<<1],segment_tree_act[i])segment_tree_act[i<<1|1]=self.f_act(segment_tree_act[i<<1|1],segment_tree_act[i])segment_tree_act[i]=self.e_actsegment_tree_act[i]=self.e_actreturn "["+", ".join(map(str,[self.operate(x,a) for x,a in zip(self.lst,segment_tree_act[self.N:])]))+"]"def __repr__(self):return "Dual_Segment_Tree("+str(self)+")"class Lazy_Segment_Tree:def __init__(self,N,f,e,f_act,e_act,operate,lst=None,bisect_search=True):self.N=Nself.f=fself.e=eself.f_act=f_actself.e_act=e_actself.operate=operateself.bisect_search=bisect_searchif self.bisect_search:self.le=1while self.le<self.N:self.le*=2else:self.le=self.Nself.segment_tree=[self.e]*(self.le+self.le)self.segment_tree_act=[self.e_act]*(self.le+self.le)if lst!=None:for i,x in enumerate(lst):self.segment_tree[i+self.le]=xfor i in range(self.le-1,0,-1):self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])self.segment_tree_act=[self.e_act]*(self.le+self.le)def __getitem__(self,i):if type(i) is int:if -self.le<=i<0:i+=self.le*2elif 0<=i<self.le:i+=self.leelse:raise IndexError("list index out of range")self.Propagate_Above(i)self.Recalculate_Above(i)return self.Operate_At(i)else:a,b,c=i.start,i.stop,i.stepif a==None or a<-self.le:a=self.leelif self.le<=a:a=self.le*2elif a<0:a+=self.le*2else:a+=self.leif b==None or self.le<=b:b=self.le*2elif b<-self.le:b=self.leelif b<0:b+=self.le*2else:b+=self.lereturn self.segment_tree[slice(a,b,c)]def __setitem__(self,i,x):if -self.le<=i<0:i+=self.le*2elif 0<=i<self.le:i+=self.leelse:raise IndexError("list index out of range")self.Propagate_Above(i)self.segment_tree[i]=xself.segment_tree_act[i]=self.e_actself.Recalculate_Above(i)def Operate_At(self,i):return self.operate(self.segment_tree[i],self.segment_tree_act[i])def Propagate_At(self,i):self.segment_tree[i]=self.Operate_At(i)self.segment_tree_act[i<<1]=self.f_act(self.segment_tree_act[i<<1],self.segment_tree_act[i])self.segment_tree_act[i<<1|1]=self.f_act(self.segment_tree_act[i<<1|1],self.segment_tree_act[i])self.segment_tree_act[i]=self.e_actdef Propagate_Above(self,i):H=i.bit_length()-1for h in range(H,0,-1):self.Propagate_At(i>>h)def Recalculate_Above(self,i):while i>1:i>>=1self.segment_tree[i]=self.f(self.Operate_At(i<<1),self.Operate_At(i<<1|1))def Build(self,lst):for i,x in enumerate(lst):self.segment_tree[i+self.le]=xfor i in range(self.le-1,0,-1):self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])self.segment_tree_act=[self.e_act]*(self.le+self.le)def Fold(self,L=None,R=None):if L==None:L=self.leelse:assert 0<=L<=self.leL+=self.leif R==None:R=self.le*2else:assert 0<=R<=self.leR+=self.leself.Propagate_Above(L//(L&-L))self.Propagate_Above(R//(R&-R)-1)vL=self.evR=self.ewhile L<R:if L&1:vL=self.f(vL,self.Operate_At(L))L+=1if R&1:R-=1vR=self.f(self.Operate_At(R),vR)L>>=1R>>=1return self.f(vL,vR)def Fold_Index(self,L=None,R=None):if L==None:L=self.leelse:assert 0<=L<=self.leL+=self.leif R==None:R=self.le*2else:assert 0<=R<=self.leR+=self.leif L==R:return Nonex=self.Fold(L-self.le,R-self.le)while L<R:if L&1:if self.segment_tree[L]==x:i=LbreakL+=1if R&1:R-=1if self.segment_tree[R]==x:i=RbreakL>>=1R>>=1while i<self.le:if self.segment_tree[i]==self.segment_tree[i<<1]:i<<=1else:i<<=1i|=1i-=self.lereturn idef Operate_Range(self,a,L=None,R=None):if L==None:L=self.leelse:assert 0<=L<=self.leL+=self.leif R==None:R=self.le*2else:assert 0<=R<=self.leR+=self.leL0=L//(L&-L)R0=R//(R&-R)-1self.Propagate_Above(L0)self.Propagate_Above(R0)while L<R:if L&1:self.segment_tree_act[L]=self.f_act(self.segment_tree_act[L],a)L+=1if R&1:R-=1self.segment_tree_act[R]=self.f_act(self.segment_tree_act[R],a)L>>=1R>>=1self.Recalculate_Above(L0)self.Recalculate_Above(R0)def Update(self):for i in range(1,self.le):self.Propagate_At(i)for i in range(self.le,self.le*2):self.segment_tree[i]=self.Operate_At(i)self.segment_tree_act[i]=self.e_actfor i in range(self.le-1,0,-1):self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])def Bisect_Right(self,L=None,f=None):assert self.bisect_searchif L==self.le:return self.leif L==None:L=0assert 0<=L<=self.leL+=self.leself.Propagate_Above(L//(L&-L))self.Propagate_Above(self.le//(self.le&-self.le)-1)l,r=L,self.le*2vl=self.evr=self.ewhile l<r:if l&1:vl=self.f(vl,self.Operate_At(l))l+=1if r&1:r-=1vr=self.f(self.Operate_At(r),vr)l>>=1r>>=1if f(self.f(vl,vr)):return self.Nv=self.eself.Propagate_Above(L)while True:while L%2==0:L>>=1vv=self.f(v,self.Operate_At(L))if f(vv):v=vvL+=1else:while L<self.le:self.Propagate_At(L)L<<=1vv=self.f(v,self.Operate_At(L))if f(vv):v=vvL+=1return L-self.ledef Bisect_Left(self,R=None,f=None):if R==0:return 0if R==None:R=self.leassert 0<=R<=self.leR+=self.leself.Propagate_Above(self.le//(self.le&-self.le))self.Propagate_Above(R//(R&-R)-1)vl=self.evr=self.el,r=self.le,Rwhile l<r:if l&1:vl=self.f(vl,self.Operate_At(l))l+=1if r&1:r-=1vr=self.f(self.Operate_At(r),vr)l>>=1r>>=1if f(self.f(vl,vr)):return 0v=self.eself.Propagate_Above(R-1)while True:R-=1while R>1 and R%2:R>>=1vv=self.f(self.Operate_At(R),v)if f(vv):v=vvelse:while R<self.le:self.Propagate_At(R)R=(R<<1)|1vv=self.f(self.Operate_At(R),v)if f(vv):v=vvR-=1return R+1-self.ledef __str__(self):import copysegment_tree=copy.deepcopy(self.segment_tree)segment_tree_act=copy.deepcopy(self.segment_tree_act)for i in range(1,self.le):segment_tree[i]=self.operate(segment_tree[i],segment_tree_act[i])segment_tree_act[i<<1]=self.f_act(segment_tree_act[i<<1],segment_tree_act[i])segment_tree_act[i<<1|1]=self.f_act(segment_tree_act[i<<1|1],segment_tree_act[i])segment_tree_act[i]=self.e_actfor i in range(self.le,self.le*2):segment_tree[i]=self.operate(segment_tree[i],segment_tree_act[i])segment_tree_act[i]=self.e_actfor i in range(self.le-1,0,-1):segment_tree[i]=self.f(segment_tree[i<<1],segment_tree[i<<1|1])return "["+", ".join(map(str,[self.operate(x,a) for x,a in zip(segment_tree[self.le:self.le+self.N],segment_tree_act[self.le:])]))+"]"def __repr__(self):return "Lazy_Segment_Tree("+str(self)+")"class Li_Chao_Tree:def __init__(self,N,X=None,inf=float("inf")):self.N=Nif X==None:self.X=[x for x in range(self.N)]else:self.X=Xself.idx={x:i for i,x in enumerate(self.X)}self.inf=infself.li_chao_tree=[(0,self.inf)]*(2*self.N)self.left,self.right=[None]*2*N,[None]*2*Nfor i in range(self.N,2*self.N):self.left[i]=self.X[i-self.N]self.right[i]=self.X[i-self.N]for i in range(self.N-1,0,-1):self.left[i]=self.left[i<<1]self.right[i]=self.right[i<<1|1]def add_line_one_segment(self,a,b,i):queue=[i]while queue:i=queue.pop()aa,bb=self.li_chao_tree[i]l=a*self.X[self.left[i]]+br=a*self.X[self.right[i]]+bll=aa*self.X[self.left[i]]+bbrr=aa*self.X[self.right[i]]+bbif ll<=l and rr<=r:continueif l<=ll and r<=rr:self.li_chao_tree[i]=(a,b)continuequeue.append(i<<1)queue.append(i<<1|1)def add_line(self,a,b,L=None,R=None):if L==None:L=self.Nelse:L+=self.Nif R==None:R=2*self.Nelse:R+=self.Nwhile L<R:if L%2:self.add_line_one_segment(a,b,L)L+=1if R%2:R-=1self.add_line_one_segment(a,b,R)L>>=1R>>=1def __call__(self,x):i=self.idx[x]+self.Nretu=self.infwhile i:a,b=self.li_chao_tree[i]retu=min(retu,a*x+b)i>>=1return retudef __getitem__(self,i):x=self.X[i]i+=self.Nretu=self.infwhile i:a,b=self.li_chao_tree[i]retu=min(retu,a*x+b)i>>=1return retudef __str__(self):li_chao_tree=[(0,self.inf)]*self.Nfor i,x in enumerate(self.X):ii=i+self.Nwhile ii:aa,bb=self.li_chao_tree[ii]a,b=li_chao_tree[i]if aa*x+bb<a*x+b:li_chao_tree[i]=aa,bbii>>=1return "["+", ".join(map(str,li_chao_tree))+"]"def __repr__(self):return "Li_Chao_Tree("+str(self)+")"N,Q=map(int,input().split())inf=10**9DST=Dual_Segment_Tree(N,max,-inf,max,[-inf]*N)query=[]for q in range(Q):l,r,B=map(int,input().split())l-=1query.append((l,r,B))DST.Operate_Range(B,l,r)ST=Segment_Tree(N,min,inf,[DST[i] for i in range(N)])for l,r,b in query:if ST.Fold(l,r)!=b:print(-1)exit()print(*[ST[i] for i in range(N)])