結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー rpy3cpprpy3cpp
提出日時 2015-06-23 00:21:58
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 1,710 ms / 5,000 ms
コード長 4,849 bytes
コンパイル時間 291 ms
コンパイル使用メモリ 13,184 KB
実行使用メモリ 19,072 KB
最終ジャッジ日時 2024-07-07 16:47:32
合計ジャッジ時間 8,887 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 27 ms
11,136 KB
testcase_01 AC 27 ms
11,008 KB
testcase_02 AC 28 ms
11,008 KB
testcase_03 AC 27 ms
11,008 KB
testcase_04 AC 29 ms
10,880 KB
testcase_05 AC 35 ms
11,008 KB
testcase_06 AC 96 ms
11,520 KB
testcase_07 AC 30 ms
11,136 KB
testcase_08 AC 40 ms
11,264 KB
testcase_09 AC 444 ms
14,848 KB
testcase_10 AC 371 ms
18,688 KB
testcase_11 AC 294 ms
13,184 KB
testcase_12 AC 446 ms
14,976 KB
testcase_13 AC 118 ms
11,776 KB
testcase_14 AC 196 ms
18,816 KB
testcase_15 AC 1,710 ms
19,072 KB
testcase_16 AC 1,196 ms
18,816 KB
testcase_17 AC 871 ms
19,072 KB
testcase_18 AC 1,417 ms
18,944 KB
testcase_19 AC 587 ms
15,488 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SplayArray(object):
    def __init__(self, size):
        self.cell_capacity = 1024
        self.size = size
        self.capacity = self._calc_capacity(size)
        self.n_cells = self.capacity // self.cell_capacity
        self.values = [0] * self.n_cells
        self.totals = [0] * (self.n_cells * 2)

    def turn_on(self, L, R):
        self._turn_on(1, self.capacity, L, R + 1)

    def turn_off(self, L, R):
        self._turn_off(1, self.capacity, L, R + 1)

    def count(self, L, R):
        if L == 0 and R == self.size - 1:  # その場しのぎの challenge01 対策
            return self.totals[1]
        else:
            return self._count(1, self.capacity, L, R + 1)

    def _calc_capacity(self, size):
        cap = self.cell_capacity
        while cap < size:
            cap <<= 1
        return cap

    def _turn_on(self, idx, cap, L, R):
        '''
        idx: self.totals 等における位置
        cap: self.totals[idx] に格納できるデータの数
        mid: 二分木における分水嶺に該当する値
        L: 開始点
        R: 終了点（Rは含まない）
        '''
        if self.totals[idx] == cap:
            return
        if L == 0 and R == cap:
            self.totals[idx] = cap
            return
        if cap == self.cell_capacity:
            idx_val = idx - self.n_cells
            if self.totals[idx] == 0:
                self.values[idx_val] = (1 << R) - (1 << L)
                self.totals[idx] = R - L
                return
            self.values[idx_val] |= (1 << R) - (1 << L)
            self.totals[idx] = bin(self.values[idx_val]).count('1')
            return
        left = idx << 1
        right = left + 1
        if self.totals[idx] == 0:
            self.totals[left] = 0
            self.totals[right] = 0
        mid = cap >> 1
        if R <= mid:
            self._turn_on(left, mid, L, R)
        elif L >= mid:
            self._turn_on(right, mid, L - mid, R - mid)
        else:
            self._turn_on(left, mid, L, mid)
            self._turn_on(right, mid, 0, R - mid)
        self.totals[idx] = self.totals[left] + self.totals[right]

    def _turn_off(self, idx, cap, L, R):
        if self.totals[idx] == 0:
            return
        if L == 0 and R == cap:
            self.totals[idx] = 0
            return
        if cap == self.cell_capacity:
            idx_val = idx - self.n_cells
            if self.totals[idx] == cap:
                self.values[idx_val] = (1 << cap) - 1 - (1 << R) + (1 << L)
                self.totals[idx] = cap - R + L
                return
            self.values[idx_val] &= ~((1 << R) - (1 << L))
            self.totals[idx] = bin(self.values[idx_val]).count('1')
            return
        left = idx << 1
        right = left + 1
        mid = cap >> 1
        if self.totals[idx] == cap:
            self.totals[left] = mid
            self.totals[right] = mid
        if R <= mid:
            self._turn_off(left, mid, L, R)
        elif L >= mid:
            self._turn_off(right, mid, L - mid, R - mid)
        else:
            self._turn_off(left, mid, L, mid)
            self._turn_off(right, mid, 0, R - mid)
        self.totals[idx] = self.totals[left] + self.totals[right]

    def _count(self, idx, cap, L, R):
        if self.totals[idx] == 0:
            return 0
        if self.totals[idx] == cap:
            return R - L
        if L == 0 and R == cap:
            return self.totals[idx]
        if cap == self.cell_capacity:
            return bin((self.values[idx - self.n_cells] >> L) & ((1 << (R - L)) - 1)).count('1')
        left = idx << 1
        right = left + 1
        mid = cap >> 1
        if R <= mid:
            return self._count(left, mid, L, R)
        if L >= mid:
            return self._count(right, mid, L - mid, R - mid)
        return self._count(left, mid, L, mid) + self._count(right, mid, 0, R - mid)

if __name__ == '__main__':
#    import time
#    start = time.time()
#    file = 'test_in/challenge01.txt'
#    f = open(file)
#    data = f.readlines()
    import sys
    data = sys.stdin.readlines()
    N = int(data[0])
    Q = int(data[1])
    teamA = SplayArray(N)
    teamB = SplayArray(N)
    scoreA = 0
    scoreB = 0
    for line in data[2:Q + 2]:
        x, l, r = map(int, line.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))
#    print(time.time() - start)
0