結果
| 問題 | No.1226 I hate Robot Arms |
| ユーザー |
 zkou
|
| 提出日時 | 2020-09-12 10:04:20 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,537 ms / 2,000 ms |
| コード長 | 5,245 bytes |
| コンパイル時間 | 653 ms |
| コンパイル使用メモリ | 86,696 KB |
| 実行使用メモリ | 134,244 KB |
| 最終ジャッジ日時 | 2023-09-16 07:23:18 |
| 合計ジャッジ時間 | 38,525 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 80 ms
72,120 KB |
| testcase_01 | AC | 78 ms
71,744 KB |
| testcase_02 | AC | 658 ms
91,528 KB |
| testcase_03 | AC | 690 ms
95,604 KB |
| testcase_04 | AC | 838 ms
103,888 KB |
| testcase_05 | AC | 771 ms
102,900 KB |
| testcase_06 | AC | 1,432 ms
129,376 KB |
| testcase_07 | AC | 646 ms
91,736 KB |
| testcase_08 | AC | 481 ms
89,684 KB |
| testcase_09 | AC | 1,022 ms
107,384 KB |
| testcase_10 | AC | 452 ms
85,076 KB |
| testcase_11 | AC | 830 ms
103,688 KB |
| testcase_12 | AC | 625 ms
92,804 KB |
| testcase_13 | AC | 563 ms
94,172 KB |
| testcase_14 | AC | 1,166 ms
114,016 KB |
| testcase_15 | AC | 407 ms
88,328 KB |
| testcase_16 | AC | 1,368 ms
128,592 KB |
| testcase_17 | AC | 630 ms
92,084 KB |
| testcase_18 | AC | 558 ms
91,492 KB |
| testcase_19 | AC | 848 ms
106,460 KB |
| testcase_20 | AC | 853 ms
104,140 KB |
| testcase_21 | AC | 1,013 ms
110,132 KB |
| testcase_22 | AC | 1,445 ms
132,556 KB |
| testcase_23 | AC | 1,384 ms
130,888 KB |
| testcase_24 | AC | 1,467 ms
131,688 KB |
| testcase_25 | AC | 1,537 ms
131,708 KB |
| testcase_26 | AC | 1,482 ms
132,200 KB |
| testcase_27 | AC | 1,373 ms
131,844 KB |
| testcase_28 | AC | 1,330 ms
134,204 KB |
| testcase_29 | AC | 1,328 ms
134,244 KB |
ソースコード
class LazySegmentTree:
__slots__ = ["n", "data", "lazy", "me", "oe", "fmm", "fmo", "foo"]
def __init__(self, monoid_data, monoid_identity, operator_identity, func_monoid_monoid, func_monoid_operator, func_operator_operator):
self.me = monoid_identity
self.oe = operator_identity
self.fmm = func_monoid_monoid
self.fmo = func_monoid_operator
self.foo = func_operator_operator
self.n = len(monoid_data)
self.data = monoid_data * 2
for i in range(self.n-1, 0, -1):
self.data[i] = self.fmm(self.data[2*i], self.data[2*i+1])
self.lazy = [self.oe] * (self.n * 2)
def replace(self, index, value):
index += self.n
# propagation
for shift in range(index.bit_length()-1, 0, -1):
i = index >> shift
self.lazy[2*i] = self.foo(self.lazy[2*i], self.lazy[i])
self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
self.data[i] = self.fmo(self.data[i], self.lazy[i])
self.lazy[i] = self.oe
# update
self.data[index] = value
self.lazy[index] = self.oe
# recalculation
i = index
while i > 1:
i //= 2
self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
self.lazy[i] = self.oe
def effect(self, l, r, operator):
l += self.n
r += self.n
l0 = l
r0 = r - 1
while l0 % 2 == 0:
l0 //= 2
while r0 % 2 == 1:
r0 //= 2
# propagation
for shift in range(l0.bit_length()-1, 0, -1):
i = l0 >> shift
self.lazy[2*i] = self.foo(self.lazy[2*i], self.lazy[i])
self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
self.data[i] = self.fmo(self.data[i], self.lazy[i])
self.lazy[i] = self.oe
for shift in range(r0.bit_length()-1, 0, -1):
i = r0 >> shift
self.lazy[2*i] = self.foo(self.lazy[2*i], self.lazy[i])
self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
self.data[i] = self.fmo(self.data[i], self.lazy[i])
self.lazy[i] = self.oe
# effect
while l < r:
if l % 2:
self.lazy[l] = self.foo(self.lazy[l], operator)
l += 1
if r % 2:
r -= 1
self.lazy[r] = self.foo(self.lazy[r], operator)
l //= 2
r //= 2
# recalculation
i = l0
while i > 1:
i //= 2
self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
self.lazy[i] = self.oe
i = r0
while i > 1:
i //= 2
self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
self.lazy[i] = self.oe
def folded(self, l, r):
l += self.n
r += self.n
l0 = l
r0 = r - 1
while l0 % 2 == 0:
l0 //= 2
while r0 % 2 == 1:
r0 //= 2
# propagation
for shift in range(l0.bit_length()-1, 0, -1):
i = l0 >> shift
self.lazy[2*i] = self.foo(self.lazy[2*i], self.lazy[i])
self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
self.data[i] = self.fmo(self.data[i], self.lazy[i])
self.lazy[i] = self.oe
for shift in range(r0.bit_length()-1, 0, -1):
i = r0 >> shift
self.lazy[2*i] = self.foo(self.lazy[2*i], self.lazy[i])
self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
self.data[i] = self.fmo(self.data[i], self.lazy[i])
self.lazy[i] = self.oe
# fold
left_folded = self.me
right_folded = self.me
while l < r:
if l % 2:
left_folded = self.fmm(left_folded, self.fmo(self.data[l], self.lazy[l]))
l += 1
if r % 2:
r -= 1
right_folded = self.fmm(self.fmo(self.data[r], self.lazy[r]), right_folded)
l //= 2
r //= 2
return self.fmm(left_folded, right_folded)
def main():
import sys
from operator import add, mul
from math import pi
from cmath import rect, phase
input = sys.stdin.buffer.readline
N, Q = map(int, input().split())
lst = LazySegmentTree([complex(1, 0)] * N, 0, 1, add, mul, mul)
ans = []
for _ in range(Q):
q, *k = map(int, input().split())
if q == 0:
arg = pi * k[1] / 180 + (phase(lst.folded(k[0] - 2, k[0] - 1)) if k[0] > 1 else 0)
delta = arg - phase(lst.folded(k[0] - 1, k[0]))
lst.effect(k[0] - 1, N, rect(1, delta))
if q == 1:
lst.replace(k[0] - 1, rect(k[1], phase(lst.folded(k[0] - 1, k[0]))))
if q == 2:
ret = lst.folded(0, k[0])
ans.append(f"{ret.real:.15} {ret.imag:.15}")
print('\n'.join(ans))
if __name__ == "__main__":
main()