結果
問題 | No.1226 I hate Robot Arms |
ユーザー | 👑 Kazun |
提出日時 | 2020-09-11 23:03:40 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,409 ms / 2,000 ms |
コード長 | 3,532 bytes |
コンパイル時間 | 923 ms |
コンパイル使用メモリ | 87,148 KB |
実行使用メモリ | 157,116 KB |
最終ジャッジ日時 | 2023-08-30 10:19:39 |
合計ジャッジ時間 | 32,455 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 72 ms
71,904 KB |
testcase_01 | AC | 73 ms
71,932 KB |
testcase_02 | AC | 549 ms
95,660 KB |
testcase_03 | AC | 575 ms
102,364 KB |
testcase_04 | AC | 652 ms
120,092 KB |
testcase_05 | AC | 610 ms
117,976 KB |
testcase_06 | AC | 1,409 ms
156,756 KB |
testcase_07 | AC | 481 ms
95,676 KB |
testcase_08 | AC | 338 ms
101,392 KB |
testcase_09 | AC | 898 ms
117,932 KB |
testcase_10 | AC | 332 ms
84,604 KB |
testcase_11 | AC | 703 ms
122,988 KB |
testcase_12 | AC | 474 ms
100,508 KB |
testcase_13 | AC | 415 ms
107,160 KB |
testcase_14 | AC | 1,008 ms
125,276 KB |
testcase_15 | AC | 290 ms
99,468 KB |
testcase_16 | AC | 1,252 ms
154,572 KB |
testcase_17 | AC | 473 ms
97,744 KB |
testcase_18 | AC | 391 ms
93,700 KB |
testcase_19 | AC | 714 ms
124,032 KB |
testcase_20 | AC | 657 ms
120,988 KB |
testcase_21 | AC | 819 ms
130,828 KB |
testcase_22 | AC | 1,233 ms
155,596 KB |
testcase_23 | AC | 1,242 ms
155,824 KB |
testcase_24 | AC | 1,264 ms
156,004 KB |
testcase_25 | AC | 1,301 ms
157,116 KB |
testcase_26 | AC | 1,249 ms
155,928 KB |
testcase_27 | AC | 1,365 ms
152,656 KB |
testcase_28 | AC | 1,329 ms
150,968 KB |
testcase_29 | AC | 1,317 ms
151,364 KB |
ソースコード
from math import sin,cos,atan2,sqrt,radians,pi class Segment_Tree(): def __init__(self,L,calc,unit): """calcを演算とするリストLのSegment Treeを作成 calc:演算(2変数関数,モノイド) unit:モノイドcalcの単位元 (xe=ex=xを満たすe) """ 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): """第k要素をxに変え,更新を行う. 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): """以下の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):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)))