結果

問題 No.1290 Addition and Subtraction Operation
ユーザー lam6er
提出日時 2025-03-31 17:36:32
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 213 ms / 2,000 ms
コード長 1,561 bytes
コンパイル時間 249 ms
コンパイル使用メモリ 82,692 KB
実行使用メモリ 122,616 KB
最終ジャッジ日時 2025-03-31 17:37:15
合計ジャッジ時間 11,128 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 85
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

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])
        R = int(input[ptr+1])
        intervals.append((L, R))
        ptr += 2
    
    # Compute t array
    t = [0] * (N + 2)  # t[0..N+1], but j ranges from 1 to N
    for j in range(1, N + 1):
        t[j] = B[j - 1] * ((-1) ** j)
    
    # Compute delta array
    delta = [0] * (N + 2)  # delta[1..N+1]
    for j in range(1, N + 1):
        delta[j] = t[j] - t[j - 1]
    delta[N + 1] = 0 - t[N]
    
    # Build adjacency list
    adj = [[] for _ in range(N + 2)]  # nodes 1..N+1
    for L, R in intervals:
        u = L
        v = R + 1
        adj[u].append(v)
        adj[v].append(u)
    
    visited = [False] * (N + 2)
    sum_ok = True
    
    for j in range(1, N + 2):
        if not visited[j]:
            q = deque()
            q.append(j)
            visited[j] = True
            total = 0
            while q:
                node = q.popleft()
                total += delta[node]
                for neighbor in adj[node]:
                    if not visited[neighbor]:
                        visited[neighbor] = True
                        q.append(neighbor)
            if total != 0:
                sum_ok = False
                break
    
    print("YES" if sum_ok else "NO")

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