結果
| 問題 |
No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
|
| コンテスト | |
| ユーザー |
 rpy3cpp
|
| 提出日時 | 2015-06-21 20:48:11 |
| 言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
| 結果 |
AC
|
| 実行時間 | 4,018 ms / 5,000 ms |
| コード長 | 6,857 bytes |
| コンパイル時間 | 80 ms |
| コンパイル使用メモリ | 13,184 KB |
| 実行使用メモリ | 11,648 KB |
| 最終ジャッジ日時 | 2024-07-07 15:57:15 |
| 合計ジャッジ時間 | 19,609 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 17 |
ソースコード
class NestedSplayArray(object):
def __init__(self, n, cell_size = None):
self.n = n
if cell_size == None:
cell_size = 32
while cell_size * 32 < n:
cell_size *= 32
self.cell_size = cell_size
self.length = n // self.cell_size + (1 if n % self.cell_size else 0)
if self.cell_size <= 1024:
self.cells = [SplayArray(self.cell_size) for i in range(self.length)]
else:
self.cells = [NestedSplayArray(self.cell_size) for i in range(self.length)]
self.all_off = True
self.all_on = False
self.total = 0
def _clear_lazy_eval(self):
if self.all_on:
for cell in self.cells:
cell.turn_on(0, self.cell_size - 1)
self.all_on = False
if self.all_off:
for cell in self.cells:
cell.turn_off(0, self.cell_size - 1)
self.all_off = False
def _get_range(self, L, R):
idxL, posL = divmod(L, self.cell_size)
idxR, posR = divmod(R, self.cell_size)
return idxL, posL, idxR, posR
def turn_on(self, L, R):
if L == 0 and R == self.n - 1:
self.all_on = True
self.all_off = False
self.total = self.n
return
self._clear_lazy_eval()
self.total = -1
idxL, posL, idxR, posR = self._get_range(L, R)
if idxL == idxR:
self.cells[idxL].turn_on(posL, posR)
else:
self.cells[idxL].turn_on(posL, self.cell_size - 1)
self.cells[idxR].turn_on(0, posR)
for idx in range(idxL + 1, idxR):
self.cells[idx].turn_on(0, self.cell_size - 1)
def turn_off(self, L, R):
'''[l, r] の範囲を off にする。
'''
if L == 0 and R == self.n - 1:
self.all_off = True
self.all_on = False
self.total = 0
return
self._clear_lazy_eval()
self.total = -1
idxL, posL, idxR, posR = self._get_range(L, R)
if idxL == idxR:
self.cells[idxL].turn_off(posL, posR)
else:
self.cells[idxL].turn_off(posL, self.cell_size - 1)
self.cells[idxR].turn_off(0, posR)
for idx in range(idxL + 1, idxR):
self.cells[idx].turn_off(0, self.cell_size - 1)
def count(self, L, R):
'''[l, r] の範囲の on の個数を返す。
'''
is_all_range = (L == 0 and R == self.n - 1)
if self.all_on:
return R - L + 1
if self.all_off:
return 0
if is_all_range and self.total != -1:
return self.total
idxL, posL, idxR, posR = self._get_range(L, R)
if idxL == idxR:
return self.cells[idxL].count(posL, posR)
counts = self.cells[idxL].count(posL, self.cell_size - 1)
counts += self.cells[idxR].count(0, posR)
for idx in range(idxL + 1, idxR):
counts += self.cells[idx].count(0, self.cell_size - 1)
if is_all_range:
self.total = counts
return counts
class SplayArray(object):
def __init__(self, n, cell_size = 32):
self.n = n
self.cell_size = cell_size
self.full = (1 << self.cell_size) - 1
self.length = n // cell_size + (1 if n % cell_size else 0)
self.cells = [0] * self.length
self.all_off = True
self.all_on = False
self.total = 0
def _clear_lazy_eval(self):
if self.all_on:
self.cells = [self.full] * self.length
self.all_on = False
if self.all_off:
self.cells = [0] * self.length
self.all_off = False
def _get_range(self, L, R):
idxL, posL = divmod(L, self.cell_size)
idxR, posR = divmod(R, self.cell_size)
return idxL, posL, idxR, posR
def turn_on(self, L, R):
'''[l, r] の範囲を on にする。
'''
if L == 0 and R == self.n - 1:
self.all_on = True
self.all_off = False
self.total = self.n
return
self._clear_lazy_eval()
self.total = -1
idxL, posL, idxR, posR = self._get_range(L, R)
if idxL == idxR:
self.cells[idxL] |= (1 << (posR + 1)) - (1 << posL)
else:
self.cells[idxL] |= (1 << self.cell_size) - (1 << posL)
self.cells[idxR] |= (1 << (posR + 1)) - 1
self.cells[idxL + 1 : idxR] = [self.full] * (idxR - idxL - 1)
def turn_off(self, L, R):
'''[l, r] の範囲を off にする。
'''
if L == 0 and R == self.n - 1:
self.all_off = True
self.all_on = False
self.total = 0
return
self._clear_lazy_eval()
self.total = -1
idxL, posL, idxR, posR = self._get_range(L, R)
if idxL == idxR:
self.cells[idxL] &= ~((1 << (posR + 1)) - (1 << posL))
else:
self.cells[idxL] &= ~((1 << self.cell_size) - (1 << posL))
self.cells[idxR] &= ~((1 << (posR + 1)) - 1)
self.cells[idxL + 1 : idxR] = [0] * (idxR - idxL - 1)
def count(self, L, R):
'''[l, r] の範囲の on の個数を返す。
'''
is_all_range = (L == 0 and R == self.n - 1)
if self.all_on:
return R - L + 1
if self.all_off:
return 0
if is_all_range and self.total != -1:
return self.total
idxL, posL, idxR, posR = self._get_range(L, R)
if idxL == idxR:
return bin(self.cells[idxL] & ((1 << (posR + 1)) - (1 << posL))).count('1')
counts = bin(self.cells[idxL] & ((1 << self.cell_size) - (1 << posL))).count('1')
counts += bin(self.cells[idxR] & ((1 << (posR + 1)) - 1)).count('1')
for idx in range(idxL + 1, idxR):
counts += bin(self.cells[idx]).count('1')
if is_all_range:
self.total = counts
return counts
if __name__ == '__main__':
N = int(input())
Q = int(input())
teamA = NestedSplayArray(N)
teamB = NestedSplayArray(N)
scoreA = 0
scoreB = 0
for q in range(Q):
x, l, r = map(int, input().split())
if x == 0:
bonusA = teamA.count(l, r)
bonusB = teamB.count(l, r)
if bonusA > bonusB:
scoreA += bonusA
elif bonusA < bonusB:
scoreB += bonusB
elif x == 1:
teamA.turn_on(l, r)
teamB.turn_off(l, r)
elif x == 2:
teamA.turn_off(l, r)
teamB.turn_on(l, r)
scoreA += teamA.count(0, N-1)
scoreB += teamB.count(0, N-1)
print('{} {}'.format(scoreA, scoreB))