結果
問題 | No.1226 I hate Robot Arms |
ユーザー |
![]() |
提出日時 | 2021-01-06 19:22:52 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,606 ms / 2,000 ms |
コード長 | 6,243 bytes |
コンパイル時間 | 479 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 177,712 KB |
最終ジャッジ日時 | 2024-11-07 05:38:28 |
合計ジャッジ時間 | 38,775 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 28 |
ソースコード
# 遅延セグ木解class LazySegmentTree:def __init__(self, op_X, e_X, mapping, compose, id_M, N, array=None):__slots__ = ["op_X","e_X","mapping","compose","id_M","N","log","N0","data","lazy"]self.e_X = e_X; self.op_X = op_X; self.mapping = mapping; self.compose = compose; self.id_M = id_Mself.N = Nself.log = (N-1).bit_length()self.N0 = 1<<self.logself.data = [e_X]*(2*self.N0)self.lazy = [id_M]*self.N0if array is not None:assert N == len(array)self.data[self.N0:self.N0+self.N] = arrayfor i in range(self.N0-1,0,-1): self.update(i)# 1点更新def point_set(self, p, x):p += self.N0for i in range(self.log, 0,-1):self.push(p>>i)self.data[p] = xfor i in range(1, self.log + 1):self.update(p>>i)# 1点取得def point_get(self, p):p += self.N0for i in range(self.log, 0, -1):self.push(p>>i)return self.data[p]# 半開区間[L,R)をopでまとめるdef prod(self, l, r):if l == r: return self.e_Xl += self.N0r += self.N0for i in range(self.log, 0, -1):if (l>>i)<<i != l:self.push(l>>i)if (r>>i)<<i != r:self.push(r>>i)sml = smr = self.e_Xwhile l < r:if l & 1:sml = self.op_X(sml, self.data[l])l += 1if r & 1:r -= 1smr = self.op_X(self.data[r], smr)l >>= 1r >>= 1return self.op_X(sml, smr)# 全体をopでまとめるdef all_prod(self): return self.data[1]# 1点作用def apply(self, p, f):p += self.N0for i in range(self.log, 0, -1):self.push(p>>i)self.data[p] = self.mapping(f, self.data[p])for i in range(1, self.log + 1):self.update(p>>i)# 区間作用def apply(self, l, r, f):if l == r: returnl += self.N0r += self.N0for i in range(self.log, 0, -1):if (l>>i)<<i != l:self.push(l>>i)if (r>>i)<<i != r:self.push((r-1)>>i)l2, r2 = l, rwhile l < r:if l & 1:self.all_apply(l, f)l += 1if r & 1:r -= 1self.all_apply(r, f)l >>= 1r >>= 1l, r = l2, r2for i in range(1, self.log + 1):if (l>>i)<<i != l:self.update(l>>i)if (r>>i)<<i != r:self.update((r-1)>>i)"""始点 l を固定f(x_l*...*x_{r-1}) が True になる最大の rつまり TTTTFFFF となるとき、F となる最小の添え字存在しない場合 n が返るf(e_M) = True でないと壊れる"""def max_right(self, l, g):if l == self.N: return self.Nl += self.N0for i in range(self.log, 0, -1): self.push(l>>i)sm = self.e_Xwhile True:while l&1 == 0:l >>= 1if not g(self.op_X(sm, self.data[l])):while l < self.N0:self.push(l)l *= 2if g(self.op_X(sm, self.data[l])):sm = self.op_X(sm, self.data[l])l += 1return l - self.N0sm = self.op_X(sm, self.data[l])l += 1if l&-l == l: breakreturn self.N"""終点 r を固定f(x_l*...*x_{r-1}) が True になる最小の lつまり FFFFTTTT となるとき、T となる最小の添え字存在しない場合 r が返るf(e_M) = True でないと壊れる"""def min_left(self, r, g):if r == 0: return 0r += self.N0for i in range(self.log, 0, -1): self.push((r-1)>>i)sm = self.e_Xwhile True:r -= 1while r>1 and r&1:r >>= 1if not g(self.op_X(self.data[r], sm)):while r < self.N0:self.push(r)r = 2*r + 1if g(self.op_X(self.data[r], sm)):sm = self.op_X(self.data[r], sm)r -= 1return r + 1 - self.N0sm = self.op_X(self.data[r], sm)if r&-r == r: breakreturn 0# 以下内部関数def update(self, k):self.data[k] = self.op_X(self.data[2*k], self.data[2*k+1])def all_apply(self, k, f):self.data[k] = self.mapping(f, self.data[k])if k < self.N0:self.lazy[k] = self.compose(f, self.lazy[k])def push(self, k): #propagate と同じif self.lazy[k] is self.id_M: returnself.data[2*k ] = self.mapping(self.lazy[k], self.data[2*k])self.data[2*k+1] = self.mapping(self.lazy[k], self.data[2*k+1])if 2*k < self.N0:self.lazy[2*k] = self.compose(self.lazy[k], self.lazy[2*k])self.lazy[2*k+1] = self.compose(self.lazy[k], self.lazy[2*k+1])self.lazy[k] = self.id_Mfrom math import cos,sin,radians,pi,sqrtn,q = map(int,input().split())def f(a,b):x = a[0]+b[0]y = a[1]+b[1]return [x,y]def mapping(a,b):rotate = [[cos(radians(a)),-sin(radians(a))],[sin(radians(a)),cos(radians(a))]]x = b[0]*rotate[0][0]+b[1]*rotate[0][1]y = b[0]*rotate[1][0]+b[1]*rotate[1][1]return [x,y]def compose(a,b):return (a+b)%360seg = LazySegmentTree(f,[0,0],mapping,compose,0,n,[[1,0] for i in range(n)])arg = [0]*nlength = [1]*nfor _ in range(q):query = list(map(int,input().split()))if query[0] == 0:i,x = query[1:]seg.apply(i-1,n,(x-arg[i-1])%360)arg[i-1] = xelif query[0] == 1:i,x = query[1:]p,q = seg.point_get(i-1)l = sqrt(p**2+q**2)seg.point_set(i-1,[p*(x/l),q*(x/l)])else:i = query[1]print(*seg.prod(0,i))