結果
問題 |
No.1219 Mancala Combo
|
ユーザー |
|
提出日時 | 2020-09-09 12:21:13 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,525 bytes |
コンパイル時間 | 464 ms |
コンパイル使用メモリ | 82,156 KB |
実行使用メモリ | 107,696 KB |
最終ジャッジ日時 | 2024-12-14 17:04:26 |
合計ジャッジ時間 | 4,551 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 WA * 13 |
ソースコード
#!/usr/bin python3 # -*- coding: utf-8 -*- # Binary Indexed Tree # 1-indexed # sum(r) :閉区間 [0,r) の合計を取得する # [8] a0 ・ a1 ・ a2 ・ a3 ・ a4 ・ a5 ・ a6 ・ a7 # [4] a0 ・ a1 ・ a2 ・ a3 # [2] a0 ・ a1 [6] a4 ・ a5 # [1] a0 [3] a2 [5] a4 [7] a6 # [1000] # [0100] # [0010] [0110] # [0001] [0011] [0111] [1111] class BinaryIndexedTree: # 初期化処理 def __init__(self, size): self.size = size self.dat = [0]*(size+1) def add(self, i, x): i += 1 while i <= self.size: self.dat[i] += x i += i & -i # 更新すべき位置 def sum(self, r): r += 1 ret = 0 while r>0: ret += self.dat[r] r -= r & -r # 加算すべき位置 return ret def init(self, a): for i, x in enumerate(a): self.add(i, x) def initrng(self, a): self.add(0, a[0]) for i in range(1,n): self.add(i, a[i]-a[i-1]) n = int(input()) a = list(map(int, input().split())) ### 区間に対する更新 bit = BinaryIndexedTree(n+1) bit.initrng(a) for j in range(n, 0, -1): for i in range(j): x = bit.sum(i) if x>i+1: print('No') exit() if x==i+1: bit.add(0,1) bit.add(i,-i-2) bit.add(i+1,i+1) # ret = [bit.sum(i) for i in range(n)] print('Yes')