結果

問題 No.230 Splarraay スプラレェーイ
ユーザー Kiri8128Kiri8128
提出日時 2020-04-26 15:53:56
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 918 ms / 5,000 ms
コード長 4,087 bytes
コンパイル時間 162 ms
コンパイル使用メモリ 82,584 KB
実行使用メモリ 97,232 KB
最終ジャッジ日時 2024-11-17 10:09:07
合計ジャッジ時間 9,114 ms
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

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

class SegmentTree():
def __init__(self, init, unitX, unitA, f, g, h):
self.f = f # (X, X) -> X
self.g = g # (X, A, i) -> X
self.h = h # (A, A) -> A
self.unitX = unitX
self.unitA = unitA
self.f = f
if type(init) == int:
self.n = init
# self.n = 1 << (self.n - 1).bit_length()
self.X = [unitX] * (self.n * 2)
self.size = [1] * (self.n * 2)
else:
self.n = len(init)
# self.n = 1 << (self.n - 1).bit_length()
self.X = [unitX] * self.n + init + [unitX] * (self.n - len(init))
self.size = [0] * self.n + [1] * len(init) + [0] * (self.n - len(init))
for i in range(self.n-1, 0, -1):
self.X[i] = self.f(self.X[i*2], self.X[i*2|1])
for i in range(self.n - 1, 0, -1):
self.size[i] = self.size[i*2] + self.size[i*2|1]
self.A = [unitA] * (self.n * 2)
def update(self, i, x):
i += self.n
self.X[i] = x
i >>= 1
while i:
self.X[i] = self.f(self.X[i*2], self.X[i*2|1])
i >>= 1
def calc(self, i):
return self.g(self.X[i], self.A[i], self.size[i])
def calc_above(self, i):
i >>= 1
while i:
self.X[i] = self.f(self.calc(i*2), self.calc(i*2|1))
i >>= 1
def propagate(self, i):
self.X[i] = self.g(self.X[i], self.A[i], self.size[i])
self.A[i*2] = self.h(self.A[i*2], self.A[i])
self.A[i*2|1] = self.h(self.A[i*2|1], self.A[i])
self.A[i] = self.unitA
def propagate_above(self, i):
H = i.bit_length()
for h in range(H, 0, -1):
self.propagate(i >> h)
def getrange(self, l, r):
l += self.n
r += self.n
l0, r0 = l // (l & -l), r // (r & -r) - 1
self.propagate_above(l0)
self.propagate_above(r0)
al = self.unitX
ar = self.unitX
while l < r:
if l & 1:
al = self.f(al, self.calc(l))
l += 1
if r & 1:
r -= 1
ar = self.f(self.calc(r), ar)
l >>= 1
r >>= 1
return self.f(al, ar)
def getvalue(self, i):
i += self.n
self.propagate_above(i)
return self.calc(i)
def operate_range(self, l, r, a):
l += self.n
r += self.n
l0, r0 = l // (l & -l), r // (r & -r) - 1
self.propagate_above(l0)
self.propagate_above(r0)
while l < r:
if l & 1:
self.A[l] = self.h(self.A[l], a)
l += 1
if r & 1:
r -= 1
self.A[r] = self.h(self.A[r], a)
l >>= 1
r >>= 1
self.calc_above(l0)
self.calc_above(r0)
def debug(self):
print("self.n =", self.n)
deX = []
deA = []
deS = []
a, b = self.n, self.n * 2
while b:
deX.append(self.X[a:b])
deA.append(self.A[a:b])
deS.append(self.size[a:b])
a, b = a//2, a
print("--- debug ---")
for d in deX[::-1]:
print(d)
print("--- ---")
for d in deA[::-1]:
print(d)
print("--- ---")
for d in deS[::-1]:
print(d)
print("--- ---")
f = lambda x, y: (x[0] + y[0], x[1] + y[1])
g = lambda x, a, s: (s, 0) if a == "A" else (0, s) if a == "B" else (x)
h = lambda a, b: b if len(b) else a
N = int(input())
st = SegmentTree(N, (0, 0), "", f, g, h)
Q = int(input())
ansa = 0
ansb = 0
for _ in range(Q):
x, l, r = map(int, input().split())
r += 1
if x == 0:
a, b = st.getrange(l, r)
if a > b:
ansa += a
elif a < b:
ansb += b
elif x == 1:
st.operate_range(l, r, "A")
else:
st.operate_range(l, r, "B")
a, b = st.getrange(0, N)
ansa += a
ansb += b
print(ansa, ansb)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0