結果

問題 No.2321 Continuous Flip
コンテスト
ユーザー qwewe
提出日時 2025-05-14 12:52:08
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,541 bytes
コンパイル時間 183 ms
コンパイル使用メモリ 82,148 KB
実行使用メモリ 191,312 KB
最終ジャッジ日時 2025-05-14 12:54:58
合計ジャッジ時間 60,692 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 6 WA * 4 TLE * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

class SegmentTreeNode:
    def __init__(self, l, r):
        self.l = l
        self.r = r
        self.left = None
        self.right = None
        self.sum_even = 0
        self.sum_odd = 0
        self.flip = False

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.root = self.build(0, self.n - 1, data)
    
    def build(self, l, r, data):
        node = SegmentTreeNode(l, r)
        if l == r:
            node.sum_even = data[l]
            node.sum_odd = 0
            return node
        mid = (l + r) // 2
        node.left = self.build(l, mid, data)
        node.right = self.build(mid+1, r, data)
        node.sum_even = node.left.sum_even + node.right.sum_even
        node.sum_odd = node.left.sum_odd + node.right.sum_odd
        return node
    
    def _push(self, node):
        if node.flip and node.left:
            node.left.sum_even, node.left.sum_odd = node.left.sum_odd, node.left.sum_even
            node.left.flip = not node.left.flip
            node.right.sum_even, node.right.sum_odd = node.right.sum_odd, node.right.sum_even
            node.right.flip = not node.right.flip
            node.flip = False
    
    def range_flip(self, l, r):
        self._range_flip(self.root, l, r)
    
    def _range_flip(self, node, l, r):
        if node.r < l or node.l > r:
            return
        if l <= node.l and node.r <= r:
            node.sum_even, node.sum_odd = node.sum_odd, node.sum_even
            node.flip = not node.flip
            return
        self._push(node)
        self._range_flip(node.left, l, r)
        self._range_flip(node.right, l, r)
        node.sum_even = node.left.sum_even + node.right.sum_even
        node.sum_odd = node.left.sum_odd + node.right.sum_odd
    
    def query_range(self, l, r):
        return self._query_range(self.root, l, r)
    
    def _query_range(self, node, l, r):
        if node.r < l or node.l > r:
            return (0, 0)
        if l <= node.l and node.r <= r:
            return (node.sum_even, node.sum_odd)
        self._push(node)
        left_even, left_odd = self._query_range(node.left, l, r)
        right_even, right_odd = self._query_range(node.right, l, r)
        return (left_even + right_even, left_odd + right_odd)

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr +=1
    M = int(input[ptr])
    ptr +=1
    C = int(input[ptr])
    ptr +=1
    A = list(map(int, input[ptr:ptr+N]))
    ptr +=N
    ops = []
    prefix = [0]*(N+1)
    for i in range(N):
        prefix[i+1] = prefix[i] + A[i]
    for _ in range(M):
        L = int(input[ptr])-1
        ptr +=1
        R = int(input[ptr])-1
        ptr +=1
        ops.append( (L, R) )
    # Compute initial gains and sort
    sorted_ops = []
    for L, R in ops:
        sum_A = prefix[R+1] - prefix[L]
        initial_gain = sum_A - C
        sorted_ops.append( ( -initial_gain, L, R ) )  # Use negative for min-heap
    # Sort in descending order of initial_gain
    sorted_ops.sort()
    # Now, process in order of increasing negative gain (so original initial_gain descending)
    st = SegmentTree(A)
    total = 0
    for neg_gain, L, R in sorted_ops:
        initial_gain = -neg_gain
        # But we need to compute current gain
        sum_even, sum_odd = st.query_range(L, R)
        current_gain = (sum_even - sum_odd) - C
        if current_gain > 0:
            total += current_gain
            st.range_flip(L, R)
    print(total)

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