結果
問題 | No.1558 Derby Live |
ユーザー |
👑 ![]() |
提出日時 | 2021-06-25 21:49:25 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 5,336 bytes |
コンパイル時間 | 182 ms |
コンパイル使用メモリ | 82,400 KB |
実行使用メモリ | 70,528 KB |
最終ジャッジ日時 | 2024-06-25 08:22:58 |
合計ジャッジ時間 | 3,880 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | RE * 33 |
ソースコード
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)#==================================================def calc(x,y):return [y[x[i]] for i in range(N+1)]#==================================================import sysfrom operator import addinput=sys.stdin.readlinewrite=sys.stdout.writeN,M,Q=map(int,input().split())unit=list(range(N+1))Rank=Segment_Tree([unit for _ in range(N+1)],calc,unit,0)Ans=[]for _ in range(Q):T,*Query=map(int,input().split())if T==1:D,*P=QueryRank.update(D,[0]+P,0)elif T==2:S,=QueryP=Rank.product(1,S,0)[1:]H=[0]*(N+1)for i in range(1,N+1):H[P[i-1]]=iAns.append(" ".join(map(str,H[1:])))else:L,R=QueryP=Rank.product(1,S,0)[1:]K=0for i in range(1,N+1):K+=abs(i-P[i-1])Ans.append(str(K))write("\n".join(Ans))