結果
問題 |
No.1290 Addition and Subtraction Operation
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()