結果

問題 No.1290 Addition and Subtraction Operation
コンテスト
ユーザー lam6er
提出日時 2025-04-09 20:58:09
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 272 ms / 2,000 ms
コード長 2,126 bytes
コンパイル時間 177 ms
コンパイル使用メモリ 82,364 KB
実行使用メモリ 125,364 KB
最終ジャッジ日時 2025-04-09 21:00:01
合計ジャッジ時間 10,707 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 85
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from sys import stdin
from collections import defaultdict

def main():
    input = sys.stdin.read().split()
    ptr = 0
    n, m = int(input[ptr]), int(input[ptr+1])
    ptr += 2
    B = list(map(int, input[ptr:ptr+n]))
    ptr += n
    LRs = []
    nodes_set = set()
    for _ in range(m):
        L = int(input[ptr])
        R = int(input[ptr+1])
        ptr += 2
        LRs.append((L, R))
        nodes_set.add(L)
        nodes_set.add(R + 1)
    
    # Compute D array (D[0] is 0, D[1..n] are computed)
    D = [0] * (n + 1)
    for j in range(1, n + 1):
        D[j] = B[j - 1] * ((-1) ** j)
    
    # Check nodes not in nodes_set and <=n must have diff[j] = 0
    for j in range(1, n + 1):
        if j not in nodes_set:
            if j == 1:
                current_diff = D[1]
            else:
                current_diff = D[j] - D[j-1]
            if current_diff != 0:
                print("NO")
                return
    
    # Prepare Union-Find for nodes in nodes_set
    parent = {}
    for node in nodes_set:
        parent[node] = node
    
    def find(u):
        while parent[u] != u:
            parent[u] = parent[parent[u]]
            u = parent[u]
        return u
    
    def union(u, v):
        u_root = find(u)
        v_root = find(v)
        if u_root != v_root:
            parent[v_root] = u_root
    
    for L, R in LRs:
        j1 = L
        j2 = R + 1
        union(j1, j2)
    
    # Group nodes by root
    groups = defaultdict(list)
    for node in parent:
        root = find(node)
        groups[root].append(node)
    
    # Calculate sum for each group
    for root in groups:
        total = 0
        for j in groups[root]:
            if j <= n:
                if j == 1:
                    diff = D[1]
                else:
                    diff = D[j] - D[j-1]
            else:
                if (j - 1) <= n:
                    diff = -D[j - 1]
                else:
                    diff = 0
            total += diff
        if total != 0:
            print("NO")
            return
    
    print("YES")

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