結果

問題 No.1226 I hate Robot Arms
ユーザー tyawanmusityawanmusi
提出日時 2020-08-30 02:18:32
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 921 ms / 2,000 ms
コード長 4,161 bytes
コンパイル時間 482 ms
コンパイル使用メモリ 82,228 KB
実行使用メモリ 120,564 KB
最終ジャッジ日時 2025-01-01 20:38:20
合計ジャッジ時間 19,644 ms
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

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

from math import cos, sin, radians
import sys
input = lambda: sys.stdin.readline().rstrip()
# SegmentTree
class SegmentTree:
def __init__(self, n, p, unit, f, g, h):
num = 2**((n-1).bit_length())
seg = [unit]*(num*2)
self.lazy = [None]*(num*2)
for i in range(n):
seg[num+i] = p[i]
for i in range(num-1, 0, -1):
seg[i] = f(seg[i << 1], seg[(i << 1)+1])
self.num = num
self.seg = seg
self.unit = unit
self.flag = False
self.f = f
self.g = g
self.h = h
def gindex(self, l, r):
l += self.num
r += self.num
lm = (l//(l & -l)) >> 1
rm = (r//(r & -r)) >> 1
mm = max(lm, rm)
r -= 1
while l < r:
if r <= rm:
yield r
if l <= lm:
yield l
l >>= 1
r >>= 1
while l:
if l <= mm:
yield l
l >>= 1
def propagates(self, ids):
num = self.num
g = self.g
h = self.h
for i in reversed(ids):
v = self.lazy[i]
if v is None:
continue
#
#
newv = v
#
#
if (i << 1) < num:
self.lazy[i << 1] = h(self.lazy[i << 1], newv)
self.lazy[(i << 1)+1] = h(self.lazy[(i << 1)+1], newv)
self.seg[i << 1] = g(self.seg[i << 1], newv)
self.seg[(i << 1)+1] = g(self.seg[(i << 1)+1], newv)
self.lazy[i] = None
def query(self, l, r):
f = self.f
if self.flag:
*ids, = self.gindex(l, r)
self.propagates(ids)
ansl = ansr = self.unit
l += self.num
r += self.num-1
if l == r:
return self.seg[l]
while l < r:
if l & 1:
ansl = f(ansl, self.seg[l])
l += 1
if r & 1 == 0:
ansr = f(self.seg[r], ansr)
r -= 1
l >>= 1
r >>= 1
if l == r:
ansl = f(ansl, self.seg[l])
return f(ansl, ansr)
def update1(self, i, x):
if self.flag:
*ids, = self.gindex(i, i+1)
self.propagates(ids)
i += self.num
f = self.f
#
self.seg[i] = (self.seg[i][0]*x,self.seg[i][1]*x)
while i:
i >>= 1
self.seg[i] = f(self.seg[i << 1], self.seg[(i << 1)+1])
def update2(self, l, r, x):
self.flag = True
*ids, = self.gindex(l, r)
self.propagates(ids)
num = self.num
f = self.f
g = self.g
h = self.h
l += num
r += num-1
if l == r:
self.seg[l] = g(self.seg[l], x)
for i in ids:
self.seg[i] = f(self.seg[i << 1], self.seg[(i << 1)+1])
return
while l < r:
if l & 1:
if l < num:
self.lazy[l] = h(self.lazy[l], x)
self.seg[l] = g(self.seg[l], x)
l += 1
if r & 1 == 0:
if r < num:
self.lazy[r] = h(self.lazy[r], x)
self.seg[r] = g(self.seg[r], x)
r -= 1
l >>= 1
r >>= 1
#
x = x
if l == r:
self.lazy[l] = h(self.lazy[l], x)
self.seg[l] = g(self.seg[l], x)
for i in ids:
self.seg[i] = f(self.seg[i << 1], self.seg[(i << 1)+1])
def update(self, i, x):
if type(i) is int:
self.update1(i, x)
else:
self.update2(i[0], i[1], x)
def f(x, y):
return (x[0]+y[0], x[1]+y[1])
def g(x, y):
a = rotate[y]
return (x[0]*a[0][0] + x[1]*a[0][1], x[0]*a[1][0] + x[1]*a[1][1])
def h(x,y):
if x is None:
return y
return (x+y) % 360
n, q = map(int, input().split())
num = 2**((n-1).bit_length())
rotate = [None]*360
for i in range(360):
rotate[i]=(
(cos(radians(i)), -sin(radians(i))),
(sin(radians(i)), cos(radians(i)))
)
seg = SegmentTree(n, [(1, 0)]*n, (0, 0), f, g, h)
theta = [0]*n
length = [1]*n
for _ in range(q):
query = tuple(map(int, input().split()))
if query[0] == 0:
_, i, x=query
seg.update((i-1, n), (x-theta[i-1]) % 360)
theta[i-1] = x
elif query[0] == 1:
_, i, x = query
seg.update(i-1, x/length[i-1])
length[i-1] = x
else:
_, i = query
x, y = seg.query(0, i)
print('{:.9f}'.format(x), '{:.9f}'.format(y))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0