結果

問題 No.1290 Addition and Subtraction Operation
コンテスト
ユーザー lam6er
提出日時 2025-03-26 15:53:33
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,546 bytes
コンパイル時間 242 ms
コンパイル使用メモリ 82,236 KB
実行使用メモリ 127,108 KB
最終ジャッジ日時 2025-03-26 15:54:32
合計ジャッジ時間 18,703 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 70 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

class FenwickTree:
    def __init__(self, size):
        self.n = size
        self.tree = [0] * (self.n + 2)  # 1-based indexing
    
    def add(self, idx, delta):
        while idx <= self.n:
            self.tree[idx] += delta
            idx += idx & -idx
    
    def query(self, idx):
        res = 0
        while idx > 0:
            res += self.tree[idx]
            idx -= idx & -idx
        return res

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    M = int(input[ptr])
    ptr += 1
    B = list(map(int, input[ptr:ptr+N]))
    ptr += N
    operations = []
    for _ in range(M):
        L = int(input[ptr])
        ptr += 1
        R = int(input[ptr])
        ptr += 1
        operations.append((L, R))
    # Sort operations in decreasing order of R, then decreasing L
    operations.sort(key=lambda x: (-x[1], -x[0]))
    max_size = N + 2
    even_tree = FenwickTree(max_size)
    odd_tree = FenwickTree(max_size)
    for (L, R) in operations:
        # Compute K_i
        current_R = R
        # Query the current contribution
        if current_R % 2 == 0:
            contrib = even_tree.query(current_R)
        else:
            contrib = odd_tree.query(current_R)
        original_B = B[current_R - 1]
        current_B_R = original_B - contrib
        # Compute exponent R - L
        exponent = current_R - L
        sign = 1 if (exponent % 2 == 0) else -1
        K_i = current_B_R * sign
        # Compute C_i = K_i * (-1)^L
        L_parity = L % 2
        c_sign = -1 if L_parity else 1
        C_i = K_i * c_sign
        # Apply range update to even and odd trees
        # Even positions in [L, R]
        start_even = L if (L % 2 == 0) else L + 1
        end_even = R if (R % 2 == 0) else R - 1
        if start_even <= end_even:
            even_tree.add(start_even, C_i)
            even_tree.add(end_even + 1, -C_i)
        # Odd positions in [L, R]
        start_odd = L if (L % 2 == 1) else L + 1
        end_odd = R if (R % 2 == 1) else R - 1
        if start_odd <= end_odd:
            odd_tree.add(start_odd, -C_i)
            odd_tree.add(end_odd + 1, C_i)
    # Check all positions
    all_zero = True
    for j in range(1, N + 1):
        if j % 2 == 0:
            contrib = even_tree.query(j)
        else:
            contrib = odd_tree.query(j)
        original = B[j - 1]
        if original - contrib != 0:
            all_zero = False
            break
    print("YES" if all_zero else "NO")

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