結果
問題 |
No.1290 Addition and Subtraction Operation
|
ユーザー |
![]() |
提出日時 | 2025-03-20 20:55:40 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,068 bytes |
コンパイル時間 | 270 ms |
コンパイル使用メモリ | 82,360 KB |
実行使用メモリ | 126,868 KB |
最終ジャッジ日時 | 2025-03-20 20:56:29 |
合計ジャッジ時間 | 17,190 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 70 WA * 15 |
ソースコード
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()