結果

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

ソースコード

diff #
raw source code 

import sys

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
    
    intervals = []
    for _ in range(M):
        L = int(input[ptr])
        ptr += 1
        R = int(input[ptr])
        ptr += 1
        intervals.append((L, R))
    
    # Sort intervals by R descending, then L descending
    intervals.sort(key=lambda x: (-x[1], -x[0]))
    
    # Compute C[j] = B[j] * (-1)^(j+1) because j starts from 1-based
    C = []
    for j in range(1, N+1):
        exponent = j
        sign = -1 if exponent % 2 else 1
        C.append(B[j-1] * sign)
    
    class BIT:
        def __init__(self, size):
            self.n = size
            self.tree = [0]*(self.n + 2)
        
        def update(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
    
    tree = BIT(N)
    
    for (L, R) in intervals:
        Li = L
        Ri = R
        # Compute s_i = (-1)^Li
        s_i = 1 if (Li % 2 == 0) else -1
        # Get current sum at Ri
        sum_prev = tree.query(Ri)
        # C array is 0-based, Ri is 1-based, so index is Ri-1
        expected = C[Ri-1]
        # Compute K_i
        numerator = (expected - sum_prev)
        K_i = numerator // s_i
        # Contribution is s_i * K_i
        contribution = s_i * K_i
        # Apply range update [Li, Ri]
        tree.update(Li, contribution)
        if Ri < N:
            tree.update(Ri + 1, -contribution)
    
    # Check all positions
    possible = True
    for j in range(1, N+1):
        current = tree.query(j)
        expected = C[j-1]
        if current != expected:
            possible = False
            break
    
    print("YES" if possible else "NO")

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