#33718 (Python3) No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ

提出ソース

結果

問題	No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー	rpy3cpp
提出日時	2015-06-21 20:48:11
言語	Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果	AC
実行時間	3,997 ms / 5,000 ms
コード長	6,857 bytes
コンパイル時間	697 ms
コンパイル使用メモリ	11,524 KB
実行使用メモリ	8,988 KB
最終ジャッジ日時	2023-09-21 22:52:17
合計ジャッジ時間	19,525 ms
ジャッジサーバーID （参考情報）	judge14 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	18 ms 8,664 KB
testcase_01	AC	20 ms 8,868 KB
testcase_02	AC	18 ms 8,584 KB
testcase_03	AC	18 ms 8,864 KB
testcase_04	AC	19 ms 8,764 KB
testcase_05	AC	26 ms 8,752 KB
testcase_06	AC	107 ms 8,764 KB
testcase_07	AC	27 ms 8,676 KB
testcase_08	AC	40 ms 8,812 KB
testcase_09	AC	1,263 ms 8,812 KB
testcase_10	AC	728 ms 8,652 KB
testcase_11	AC	614 ms 8,728 KB
testcase_12	AC	1,256 ms 8,788 KB
testcase_13	AC	169 ms 8,784 KB
testcase_14	AC	361 ms 8,868 KB
testcase_15	AC	3,997 ms 8,688 KB
testcase_16	AC	3,396 ms 8,848 KB
testcase_17	AC	2,893 ms 8,988 KB
testcase_18	AC	1,310 ms 8,888 KB
testcase_19	AC	1,604 ms 8,744 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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))

yukicoder

結果

テストケース

ソースコード