結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:44:32
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 933 ms / 5,000 ms
コード長 2,971 bytes
コンパイル時間 323 ms
コンパイル使用メモリ 82,232 KB
実行使用メモリ 122,332 KB
最終ジャッジ日時 2025-03-31 17:45:34
合計ジャッジ時間 7,564 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(1 << 25)

class SegmentTree:
    def __init__(self, size):
        self.n = size
        self.countA = [0] * (4 * self.n)
        self.countB = [0] * (4 * self.n)
        self.lazy = [0] * (4 * self.n)  # 0: none, 1: A, 2: B

    def push(self, node, start, end):
        if self.lazy[node] == 0 or start == end:
            return
        mid = (start + end) // 2
        left_node = 2 * node + 1
        right_node = 2 * node + 2

        color = self.lazy[node]
        # Assign left child
        self.lazy[left_node] = color
        self.countA[left_node] = (color == 1) * (mid - start + 1)
        self.countB[left_node] = (color == 2) * (mid - start + 1)

        # Assign right child
        self.lazy[right_node] = color
        self.countA[right_node] = (color == 1) * (end - mid)
        self.countB[right_node] = (color == 2) * (end - mid)

        # Clear current node's lazy
        self.lazy[node] = 0

    def update(self, l, r, color, node=0, start=None, end=None):
        if start is None:
            start = 0
            end = self.n - 1
        if l > end or r < start:
            return
        if l <= start and end <= r:
            self.lazy[node] = color
            self.countA[node] = (color == 1) * (end - start + 1)
            self.countB[node] = (color == 2) * (end - start + 1)
            return
        self.push(node, start, end)
        mid = (start + end) // 2
        self.update(l, r, color, 2*node+1, start, mid)
        self.update(l, r, color, 2*node+2, mid+1, end)
        self.countA[node] = self.countA[2*node+1] + self.countA[2*node+2]
        self.countB[node] = self.countB[2*node+1] + self.countB[2*node+2]

    def query(self, l, r, node=0, start=None, end=None):
        if start is None:
            start = 0
            end = self.n - 1
        if l > end or r < start:
            return (0, 0)
        if l <= start and end <= r:
            return (self.countA[node], self.countB[node])
        self.push(node, start, end)
        mid = (start + end) // 2
        left_a, left_b = self.query(l, r, 2*node+1, start, mid)
        right_a, right_b = self.query(l, r, 2*node+2, mid+1, end)
        return (left_a + right_a, left_b + right_b)

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr +=1
    Q = int(input[ptr])
    ptr +=1
    st = SegmentTree(N)
    bonus_a = 0
    bonus_b = 0
    for _ in range(Q):
        x = int(input[ptr])
        ptr +=1
        l = int(input[ptr])
        ptr +=1
        r = int(input[ptr])
        ptr +=1
        if x == 0:
            a, b = st.query(l, r)
            if a > b:
                bonus_a += a
            elif b > a:
                bonus_b += b
        elif x ==1:
            st.update(l, r, 1)
        else:
            st.update(l, r, 2)
    total_a, total_b = st.query(0, N-1)
    print(total_a + bonus_a, total_b + bonus_b)

if __name__ == "__main__":
    main()
0