結果

問題 No.1226 I hate Robot Arms
ユーザー 👑 KazunKazun
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

from math import sin,cos,atan2,sqrt,radians,pi
class Segment_Tree():
def __init__(self,L,calc,unit):
"""calcLSegment Tree
calc:(2,)
unit:calc (xe=ex=xe)
"""
self.calc=calc
self.unit=unit
N=len(L)
d=max(1,(N-1).bit_length())
k=2**d
X=[unit]*(k-1)+L+[unit]*(k-len(L))
self.num=k
self.depth=d
for i in range(k-2,-1,-1):
X[i]=calc(X[2*i+1],X[2*i+2])
self.data=X
def get(self,k,index=0):
return self.data[(self.num-1)+(k-index)]
def update(self,k,x,index=0):
"""kx,.
k:
x:
"""
m=(self.num-1)+(k-index)
self.data[m]=x
for _ in range(self.depth):
m=(m-1)//2
self.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.unit
elif 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):
"""2x1.\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):True
0<=l<=r<=n
"""
l-=index
assert 0<=l<=r<=self.num,""
assert cond(self.unit),"."
if l==r:
return r+index
l+=(self.num-1)
sm=self.unit
calc=self.calc
while True:
while l%2:
l=(l-1)>>1
if not cond(calc(sm,self.data[l])):
while l<self.num-1:
l=2*l+1
if cond(calc(sm,self.data[l])):
sm=calc(sm,self.data[l])
l+=1
return min(l-(self.num-1)+index,r)
sm=calc(sm,self.data[l])
l+=1
m=l+1
if not (m&(-m) !=m):
break
return r+index
def calc(X,Y):
r1,t1,f1=X
r2,t2,f2=Y
p=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=T
r,t,f=S.get(i,1)
S.update(i,(r,radians(theta),radians(theta)),1)
elif T[0]==1:
_,i,x=T
r,t,f=S.get(i,1)
S.update(i,(x,t,f),1)
else:
_,x=T
r,t,f=S.product(1,x,1)
X.append("{} {}".format(r*cos(t),r*sin(t)))
print("\n".join(map(str,X)))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0