結果
問題 | No.1226 I hate Robot Arms |
ユーザー | 👑 Kazun |
提出日時 | 2020-11-13 04:02:37 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,281 ms / 2,000 ms |
コード長 | 3,569 bytes |
コンパイル時間 | 835 ms |
コンパイル使用メモリ | 87,000 KB |
実行使用メモリ | 157,188 KB |
最終ジャッジ日時 | 2023-09-30 01:55:18 |
合計ジャッジ時間 | 33,891 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 74 ms
71,952 KB |
testcase_01 | AC | 71 ms
72,160 KB |
testcase_02 | AC | 438 ms
95,188 KB |
testcase_03 | AC | 497 ms
101,992 KB |
testcase_04 | AC | 593 ms
118,884 KB |
testcase_05 | AC | 556 ms
116,680 KB |
testcase_06 | AC | 1,267 ms
157,188 KB |
testcase_07 | AC | 712 ms
95,216 KB |
testcase_08 | AC | 308 ms
101,848 KB |
testcase_09 | AC | 798 ms
117,712 KB |
testcase_10 | AC | 303 ms
85,156 KB |
testcase_11 | AC | 616 ms
122,044 KB |
testcase_12 | AC | 412 ms
101,860 KB |
testcase_13 | AC | 359 ms
105,384 KB |
testcase_14 | AC | 885 ms
124,900 KB |
testcase_15 | AC | 257 ms
99,324 KB |
testcase_16 | AC | 1,136 ms
154,648 KB |
testcase_17 | AC | 484 ms
97,212 KB |
testcase_18 | AC | 360 ms
92,356 KB |
testcase_19 | AC | 678 ms
123,528 KB |
testcase_20 | AC | 621 ms
120,852 KB |
testcase_21 | AC | 789 ms
130,640 KB |
testcase_22 | AC | 1,151 ms
154,836 KB |
testcase_23 | AC | 1,281 ms
154,248 KB |
testcase_24 | AC | 1,137 ms
154,532 KB |
testcase_25 | AC | 1,202 ms
156,812 KB |
testcase_26 | AC | 1,113 ms
154,740 KB |
testcase_27 | AC | 1,148 ms
151,620 KB |
testcase_28 | AC | 1,174 ms
151,780 KB |
testcase_29 | AC | 1,162 ms
151,560 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) #================================================= import sys input=sys.stdin.readline 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)))