結果
問題 | No.1226 I hate Robot Arms |
ユーザー |
👑 ![]() |
提出日時 | 2020-09-11 23:03:40 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,181 ms / 2,000 ms |
コード長 | 3,532 bytes |
コンパイル時間 | 168 ms |
コンパイル使用メモリ | 82,484 KB |
実行使用メモリ | 155,024 KB |
最終ジャッジ日時 | 2025-01-01 21:48:58 |
合計ジャッジ時間 | 26,971 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 28 |
ソースコード
from math import sin,cos,atan2,sqrt,radians,piclass Segment_Tree():def __init__(self,L,calc,unit):"""calcを演算とするリストLのSegment Treeを作成calc:演算(2変数関数,モノイド)unit:モノイドcalcの単位元 (xe=ex=xを満たすe)"""self.calc=calcself.unit=unitN=len(L)d=max(1,(N-1).bit_length())k=2**dX=[unit]*(k-1)+L+[unit]*(k-len(L))self.num=kself.depth=dfor i in range(k-2,-1,-1):X[i]=calc(X[2*i+1],X[2*i+2])self.data=Xdef get(self,k,index=0):return self.data[(self.num-1)+(k-index)]def update(self,k,x,index=0):"""第k要素をxに変え,更新を行う.k:数列の要素x:更新後の値"""m=(self.num-1)+(k-index)self.data[m]=xfor _ in range(self.depth):m=(m-1)//2self.data[m]=self.calc(self.data[2*m+1],self.data[2*m+2])def product(self,From,To,index=0,left_closed=True,right_closed=True):A=From-index+(not left_closed)B=To-index-(not right_closed)return self.__product_second(A,B+1,0,0,self.num)def __product_second(self,a,b,k,l,r):if r<=a or b<=l:return self.unitelif a<=l and r<=b:return self.data[k]else:alpha=self.__product_second(a,b,2*k+1,l,(l+r)//2)beta=self.__product_second(a,b,2*k+2,(l+r)//2,r)return self.calc(alpha,beta)def all_prod(self):return self.data[0]def max_right(self,l,r,cond,index=0):"""以下の2つをともに満たすxの1つを返す.\n(1) r=l or cond(data[l]*data[l+1]*...*d[r-1]):True(2) r=x or cond(data[l]*data[l+1]*...*data[r]):False※fが単調減少の時,cond(data[l]*...*data[r-1])を満たす最大のrとなる.cond:関数(引数が同じならば結果も同じ)cond(unit):True0<=l<=r<=n"""l-=indexassert 0<=l<=r<=self.num,"添字が範囲外"assert cond(self.unit),"単位元が条件を満たさない."if l==r:return r+indexl+=(self.num-1)sm=self.unitcalc=self.calcwhile True:while l%2:l=(l-1)>>1if not cond(calc(sm,self.data[l])):while l<self.num-1:l=2*l+1if cond(calc(sm,self.data[l])):sm=calc(sm,self.data[l])l+=1return min(l-(self.num-1)+index,r)sm=calc(sm,self.data[l])l+=1m=l+1if not (m&(-m) !=m):breakreturn r+indexdef calc(X,Y):r1,t1,f1=Xr2,t2,f2=Yp=r1*cos(t1)+r2*cos(t2+f1)q=r1*sin(t1)+r2*sin(t2+f1)return (sqrt(p*p+q*q),atan2(q,p),f1+f2)#=================================================N,Q=map(int,input().split())A=[(1,0,0) for _ in range(N)]S=Segment_Tree(A,calc,(0,0,0))X=[]for _ in range(Q):T=tuple(map(int,input().split()))if T[0]==0:_,i,theta=Tr,t,f=S.get(i,1)S.update(i,(r,radians(theta),radians(theta)),1)elif T[0]==1:_,i,x=Tr,t,f=S.get(i,1)S.update(i,(x,t,f),1)else:_,x=Tr,t,f=S.product(1,x,1)X.append("{} {}".format(r*cos(t),r*sin(t)))print("\n".join(map(str,X)))