結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー lam6er
提出日時 2025-03-20 20:34:19
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 2,450 bytes
コンパイル時間 206 ms
コンパイル使用メモリ 82,448 KB
実行使用メモリ 113,972 KB
最終ジャッジ日時 2025-03-20 20:36:05
合計ジャッジ時間 8,673 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 4 RE * 11 TLE * 1 -- * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Node:
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.left = None
        self.right = None
        self.time = 0
        self.team = 0  # 0: unpainted, 1: A, 2: B

def update(node, l, r, team, time):
    if node.end < l or node.start > r:
        return
    if l <= node.start and node.end <= r:
        if node.time < time:
            node.time = time
            node.team = team
        return
    # Split and propagate
    if not node.left and node.start < node.end:
        mid = (node.start + node.end) // 2
        node.left = Node(node.start, mid)
        node.right = Node(mid+1, node.end)
    # Propagate current time if needed
    if node.time != 0:
        if node.left.time < node.time:
            node.left.time = node.time
            node.left.team = node.team
        if node.right.time < node.time:
            node.right.time = node.time
            node.right.team = node.team
        node.time = 0
        node.team = 0
    update(node.left, l, r, team, time)
    update(node.right, l, r, team, time)

def query_range(node, l, r):
    if node.end < l or node.start > r:
        return (0, 0)
    a = max(node.start, l)
    b = min(node.end, r)
    if a > b:
        return (0, 0)
    if node.team != 0:
        count = b - a + 1
        if node.team == 1:
            return (count, 0)
        else:
            return (0, count)
    if node.start == node.end:
        return (0, 0)
    left_a, left_b = query_range(node.left, l, r)
    right_a, right_b = query_range(node.right, l, r)
    return (left_a + right_a, left_b + right_b)

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx +=1
    Q = int(data[idx])
    idx +=1
    root = Node(0, N-1)
    timestamp = 0
    A_bonus = 0
    B_bonus = 0
    for _ in range(Q):
        x = int(data[idx])
        idx +=1
        l = int(data[idx])
        idx +=1
        r = int(data[idx])
        idx +=1
        if x == 0:
            a, b = query_range(root, l, r)
            if a > b:
                A_bonus += a
            elif b > a:
                B_bonus += b
        else:
            team = x
            timestamp +=1
            update(root, l, r, team, timestamp)
    # Final query for entire array
    total_a, total_b = query_range(root, 0, N-1)
    print(total_a + A_bonus, total_b + B_bonus)

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