結果
問題 | No.1226 I hate Robot Arms |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
from math import cos, sin, radiansimport sysinput = lambda: sys.stdin.readline().rstrip()# SegmentTreeclass 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 = numself.seg = segself.unit = unitself.flag = Falseself.f = fself.g = gself.h = hdef gindex(self, l, r):l += self.numr += self.numlm = (l//(l & -l)) >> 1rm = (r//(r & -r)) >> 1mm = max(lm, rm)r -= 1while l < r:if r <= rm:yield rif l <= lm:yield ll >>= 1r >>= 1while l:if l <= mm:yield ll >>= 1def propagates(self, ids):num = self.numg = self.gh = self.hfor 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] = Nonedef query(self, l, r):f = self.fif self.flag:*ids, = self.gindex(l, r)self.propagates(ids)ansl = ansr = self.unitl += self.numr += self.num-1if l == r:return self.seg[l]while l < r:if l & 1:ansl = f(ansl, self.seg[l])l += 1if r & 1 == 0:ansr = f(self.seg[r], ansr)r -= 1l >>= 1r >>= 1if 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.numf = self.f# 変更済みself.seg[i] = (self.seg[i][0]*x,self.seg[i][1]*x)while i:i >>= 1self.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.numf = self.fg = self.gh = self.hl += numr += num-1if 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])returnwhile 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 += 1if r & 1 == 0:if r < num:self.lazy[r] = h(self.lazy[r], x)self.seg[r] = g(self.seg[r], x)r -= 1l >>= 1r >>= 1# 変更済みx = xif 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 yreturn (x+y) % 360n, q = map(int, input().split())num = 2**((n-1).bit_length())rotate = [None]*360for 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]*nlength = [1]*nfor _ in range(q):query = tuple(map(int, input().split()))if query[0] == 0:_, i, x=queryseg.update((i-1, n), (x-theta[i-1]) % 360)theta[i-1] = xelif query[0] == 1:_, i, x = queryseg.update(i-1, x/length[i-1])length[i-1] = xelse:_, i = queryx, y = seg.query(0, i)print('{:.9f}'.format(x), '{:.9f}'.format(y))