結果

問題 No.1219 Mancala Combo
コンテスト
ユーザー osm ibt
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/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')
0