結果
問題 | No.1675 Strange Minimum Query |
ユーザー |
👑 ![]() |
提出日時 | 2021-09-11 00:58:55 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 6,498 bytes |
コンパイル時間 | 244 ms |
コンパイル使用メモリ | 82,152 KB |
実行使用メモリ | 175,036 KB |
最終ジャッジ日時 | 2024-06-12 21:33:09 |
合計ジャッジ時間 | 19,543 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 3 |
other | WA * 34 |
ソースコード
import heapqclass Heap_Dict:def __init__(self,Mode=True):"""Mode:True→最小値,False→最大値"""self.heap=[]self.dict={}self.Mode=Modedef __bool__(self):return bool(self.heap)def insert(self,x):if self.Mode and not self.is_exist(x):heapq.heappush(self.heap,x)elif not self.Mode and not self.is_exist(x):heapq.heappush(self.heap,-x)if x in self.dict:self.dict[x]+=1else:self.dict[x]=1def erase(self,x):assert (x in self.dict) and (self.dict[x])self.dict[x]-=1while self.heap:y=self.heap[0]if not self.Mode:y=-yif self.dict[y]==0:heapq.heappop(self.heap)else:breakdef is_exist(self,x):return (x in self.dict) and (self.dict[x])def get_min(self):assert self.Modeif self.heap:return self.heap[0]else:return float("inf")def get_max(self):assert not self.Modeif self.heap:return -self.heap[0]else:return -float("inf")def count(self,x):if x not in self.dict:return 0else:return self.dict[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 sysinput=sys.stdin.readlinewrite=sys.stdout.writeN,Q=map(int,input().split())X=[[] for _ in range(N+2)]M=[]for _ in range(Q):L,R,B=map(int,input().split())M.append((L,R,B))X[L].append(B)X[R+1].append(-B)H=Heap_Dict(False)H.insert(1)A=[1]*(N+2)for i in range(1,N+1):for x in X[i]:if x>0:H.insert(x)else:H.erase(-x)A[i]=H.get_max()S=Segment_Tree(A,min,10**9,0)for i in range(N+1):print(i,S[i],S.product(i,i,0))for L,R,B in M:if S.product(L,R,0)!=B:exit(print(-1))print(*A[1:N+1])