結果
| 問題 |
No.1226 I hate Robot Arms
|
| コンテスト | |
| ユーザー |
 tamato
|
| 提出日時 | 2020-09-11 23:18:49 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,660 bytes |
| コンパイル時間 | 491 ms |
| コンパイル使用メモリ | 82,808 KB |
| 実行使用メモリ | 183,236 KB |
| 最終ジャッジ日時 | 2025-01-01 22:03:28 |
| 合計ジャッジ時間 | 23,003 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 WA * 1 |
| other | WA * 28 |
ソースコード
mod = 1000000007
eps = 10**-9
def main():
import sys
from math import cos, sin, radians
input = sys.stdin.buffer.readline
def add(a, b):
return (a+b)%360
class SegmentTree:
def __init__(self, A, initialize=True, segfunc=min, ident=2000000000):
self.N = len(A)
self.LV = (self.N - 1).bit_length()
self.N0 = 1 << self.LV
self.segfunc = segfunc
self.ident = ident
if initialize:
self.data = [self.ident] * self.N0 + A + [self.ident] * (self.N0 - self.N)
for i in range(self.N0 - 1, 0, -1):
self.data[i] = segfunc(self.data[i * 2], self.data[i * 2 + 1])
else:
self.data = [self.ident] * (self.N0 * 2)
def update(self, i, x):
i += self.N0 - 1
self.data[i] = x
for _ in range(self.LV):
i >>= 1
self.data[i] = self.segfunc(self.data[i * 2], self.data[i * 2 + 1])
# open interval [l, r)
def query(self, l, r):
l += self.N0 - 1
r += self.N0 - 1
ret_l = self.ident
ret_r = self.ident
while l < r:
if l & 1:
ret_l = self.segfunc(ret_l, self.data[l])
l += 1
if r & 1:
ret_r = self.segfunc(self.data[r - 1], ret_r)
r -= 1
l >>= 1
r >>= 1
return self.segfunc(ret_l, ret_r)
# return smallest i(l <= i < r) s.t. check(A[i]) == True
def binsearch(self, l, r, check):
if not check(self.query(l, r)):
return r
l += self.N0 - 1
val = self.ident
while True:
if check(self.segfunc(val, self.data[l])):
break
if l & 1:
val = self.segfunc(val, self.data[l])
l += 1
l >>= 1
while l < self.N0:
newval = self.segfunc(val, self.data[l * 2])
if not check(newval):
val = newval
l = (l << 1) + 1
else:
l <<= 1
return l - self.N0 + 1
class LazySegTree:
# Range update query
def __init__(self, A, initialize=True, segfunc=min, ident=2 ** 31 - 1):
self.N = len(A)
self.LV = (self.N - 1).bit_length()
self.N0 = 1 << self.LV
self.segfunc = segfunc
self.ident = ident
if initialize:
self.data = [self.ident] * self.N0 + A + [self.ident] * (self.N0 - self.N)
for i in range(self.N0 - 1, 0, -1):
self.data[i] = segfunc(self.data[i * 2], self.data[i * 2 + 1])
else:
self.data = [self.ident] * (self.N0 * 2)
self.lazy = [0] * (self.N0 * 2)
self.lazy_flg = [False] * (self.N0 * 2)
self.theta = SegmentTree([0] * self.N, segfunc=add, ident=0, initialize=False)
self.length = [1] * (self.N+1)
def _ascend(self, i):
for _ in range(i.bit_length() - 1):
i >>= 1
self.data[i] = self.segfunc(self.data[i * 2], self.data[i * 2 + 1])
def _descend(self, idx):
lv = idx.bit_length()
for j in range(lv - 1, 0, -1):
i = idx >> j
x = self.lazy[i]
if not self.lazy_flg[i]:
continue
self.lazy_flg[i] = False
self.lazy[i * 2] = x
self.lazy[i * 2 + 1] = x
self.lazy_flg[i * 2] = True
self.lazy_flg[i * 2 + 1] = True
self.data[i * 2] = rotate(self.data[i*2], x)
self.data[i * 2 + 1] = rotate(self.data[i*2+1], x)
# open interval [l, r)
def update(self, l, r, x):
x_ori = self.theta.query(l, l+1)
self.theta.update(l, x)
x -= x_ori
x %= 360
l += self.N0 - 1
r += self.N0 - 1
self._descend(l // (l & -l))
self._descend(r // (r & -r) - 1)
l_ori = l
r_ori = r
while l < r:
if l & 1:
self.data[l] = rotate(self.data[l], x)
self.lazy[l] = x
self.lazy_flg[l] = True
l += 1
if r & 1:
r -= 1
self.data[r] = rotate(self.data[r], x)
self.lazy[r] = x
self.lazy_flg[r] = True
l >>= 1
r >>= 1
self._ascend(l_ori // (l_ori & -l_ori))
self._ascend(r_ori // (r_ori & -r_ori) - 1)
def update2(self, i, y):
len_ori = self.length[i]
theta_i = self.theta.query(1, i+1)
vec_plus = rotate([y - len_ori, 0], theta_i)
i += self.N0 - 1
self._descend(i // (i & -i))
self.data[i] = vecadd(self.data[i], vec_plus)
for _ in range(self.LV):
i >>= 1
self.data[i] = self.segfunc(self.data[i * 2], self.data[i * 2 + 1])
# open interval [l, r)
def query(self, l, r):
l += self.N0 - 1
r += self.N0 - 1
self._descend(l // (l & -l))
self._descend(r // (r & -r) - 1)
ret = self.ident
while l < r:
if l & 1:
ret = self.segfunc(ret, self.data[l])
l += 1
if r & 1:
ret = self.segfunc(self.data[r - 1], ret)
r -= 1
l >>= 1
r >>= 1
return ret
def vecadd(v0, v1):
return [v0[0] + v1[0], v0[1] + v1[1]]
ident = [0, 0]
def rotate(vec, x):
x = radians(x)
return [vec[0] * cos(x) - vec[1] * sin(x), vec[0] * sin(x) + vec[1] * cos(x)]
N, Q = map(int, input().split())
A = [[1, 0] for _ in range(N)]
ST = LazySegTree(A, segfunc=vecadd, ident=ident)
for _ in range(Q):
query = list(map(int, input().split()))
if query[0] == 0:
i, x = query[1:]
ST.update(i, N+1, x)
elif query[0] == 1:
i, x = query[1:]
ST.update2(i, x)
else:
i = query[1]
print(*ST.query(1, i+1))
#print(ST.data, ST.lazy)
if __name__ == '__main__':
main()