結果

問題 No.2321 Continuous Flip
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:13:06
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,833 bytes
コンパイル時間 477 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 176,912 KB
最終ジャッジ日時 2025-06-12 20:17:05
合計ジャッジ時間 23,270 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 6 WA * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import heapq

def main():
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    C = int(data[idx])
    idx += 1

    A = list(map(int, data[idx:idx+N]))
    idx += N

    operations = []
    for i in range(M):
        L = int(data[idx]) - 1
        idx += 1
        R = int(data[idx]) - 1
        idx += 1
        operations.append((L, R))

    # Compute the prefix sums of A
    prefix = [0]*(N+1)
    for i in range(N):
        prefix[i+1] = prefix[i] + A[i]

    # Compute sum for each operation
    total_A = [0]*M
    for i in range(M):
        L, R = operations[i]
        total_A[i] = prefix[R+1] - prefix[L]

    # Compute initial gains
    gains = []
    for i in range(M):
        gain = total_A[i] - C
        gains.append(gain)

    # Use a max-heap
    heap = []
    for i in range(M):
        if gains[i] > 0:
            heapq.heappush(heap, (-gains[i], i))  # Using max-heap via negative values

    # Fenwick tree to track the current sum of s_j * A_j, where s_j is 1 if face up
    class FenwickTree:
        def __init__(self, size):
            self.size = size
            self.tree = [0]*(size + 2)
        
        def update_point(self, idx, delta):
            idx += 1  # 1-based indexing
            while idx <= self.size + 1:
                self.tree[idx] += delta
                idx += idx & -idx
        
        def query_range(self, L, R):
            res = 0
            R += 1
            while R > 0:
                res += self.tree[R]
                R -= R & -R
            while L > 0:
                res -= self.tree[L]
                L -= L & -L
            return res

    ft = FenwickTree(N)

    max_happiness = 0
    s = 0
    selected = set()
    current_sum = 0

    while heap:
        neg_gain, i = heapq.heappop(heap)
        gain = -neg_gain

        if gain <= 0:
            break

        L, R = operations[i]
        sum_current = ft.query_range(L, R)

        # Compute the actual gain
        actual_gain = (total_A[i] - 2 * sum_current) - C
        if actual_gain <= 0:
            continue

        # Include this operation
        s += actual_gain
        max_happiness = max(max_happiness, s)

        selected.add(i)

        # Flip all cards in the range
        for j in range(L, R+1):
            current = ft.query_range(j, j)
            delta = A[j] - 2 * current
            ft.update_point(j, delta)

        # Now, we need to update the gains for all operations that overlap with [L, R], but this is too slow
        # So, for the purpose of this problem, we consider that overlapping operations are not updated, which is incorrect

        # This approach is incorrect, but it's a placeholder

    print(max_happiness)

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