結果
| 問題 | No.1226 I hate Robot Arms |
| ユーザー |
 zkou
|
| 提出日時 | 2020-09-12 10:04:20 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,359 ms / 2,000 ms |
| コード長 | 5,245 bytes |
| コンパイル時間 | 162 ms |
| コンパイル使用メモリ | 82,560 KB |
| 実行使用メモリ | 131,544 KB |
| 最終ジャッジ日時 | 2024-07-03 09:01:13 |
| 合計ジャッジ時間 | 33,574 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 41 ms
54,016 KB |
| testcase_01 | AC | 47 ms
54,492 KB |
| testcase_02 | AC | 595 ms
89,748 KB |
| testcase_03 | AC | 632 ms
93,784 KB |
| testcase_04 | AC | 781 ms
101,208 KB |
| testcase_05 | AC | 700 ms
100,868 KB |
| testcase_06 | AC | 1,359 ms
128,320 KB |
| testcase_07 | AC | 630 ms
89,780 KB |
| testcase_08 | AC | 431 ms
88,168 KB |
| testcase_09 | AC | 950 ms
105,092 KB |
| testcase_10 | AC | 419 ms
82,340 KB |
| testcase_11 | AC | 751 ms
103,484 KB |
| testcase_12 | AC | 554 ms
91,920 KB |
| testcase_13 | AC | 505 ms
92,704 KB |
| testcase_14 | AC | 1,034 ms
111,004 KB |
| testcase_15 | AC | 355 ms
86,620 KB |
| testcase_16 | AC | 1,269 ms
127,096 KB |
| testcase_17 | AC | 540 ms
90,476 KB |
| testcase_18 | AC | 491 ms
87,588 KB |
| testcase_19 | AC | 755 ms
103,912 KB |
| testcase_20 | AC | 766 ms
102,624 KB |
| testcase_21 | AC | 929 ms
109,576 KB |
| testcase_22 | AC | 1,339 ms
130,604 KB |
| testcase_23 | AC | 1,275 ms
128,444 KB |
| testcase_24 | AC | 1,339 ms
129,776 KB |
| testcase_25 | AC | 1,358 ms
129,548 KB |
| testcase_26 | AC | 1,330 ms
130,084 KB |
| testcase_27 | AC | 1,286 ms
130,400 KB |
| testcase_28 | AC | 1,215 ms
131,544 KB |
| testcase_29 | AC | 1,247 ms
130,692 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()