結果

問題 No.1219 Mancala Combo
ユーザー 双六
提出日時 2020-09-07 02:19:53
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 634 ms / 2,000 ms
コード長 2,229 bytes
コンパイル時間 174 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 114,176 KB
最終ジャッジ日時 2024-11-29 08:01:21
合計ジャッジ時間 5,818 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")
def getlist():
return list(map(int, input().split()))
class lazySegTree(object):
def __init__(self, N):
self.N = N
self.LV = (N - 1).bit_length()
self.N0 = 2 ** self.LV
self.initVal = 0
self.data = [0] * (2 * self.N0)
self.lazy = [0] * (2 * self.N0)
def calc(self, a, b):
return a + b
def initialize(self, A):
for i in range(self.N):
self.data[self.N0 - 1 + i] = A[i]
for i in range(self.N0 - 2, -1, -1):
self.data[i] = self.calc(self.data[2 * i + 1], self.data[2 * i + 2])
def gindex(self, l, r):
L = (l + self.N0) >> 1; R = (r + self.N0) >> 1
lc = 0 if l & 1 else (L & -L).bit_length()
rc = 0 if r & 1 else (R & -R).bit_length()
for i in range(self.LV):
if rc <= i:
yield R
if L < R and lc <= i:
yield L
L >>= 1; R >>= 1
def propagates(self, *ids):
for i in reversed(ids):
v = self.lazy[i - 1]
if not v:
continue
self.lazy[2 * i - 1] += v; self.lazy[2 * i] += v
self.data[2 * i - 1] += v; self.data[2 * i] += v
self.lazy[i - 1] = 0
def update(self, l, r, x):
*ids, = self.gindex(l, r + 1)
self.propagates(*ids)
L = self.N0 + l; R = self.N0 + r + 1
while L < R:
if R & 1:
R -= 1
self.lazy[R - 1] += x; self.data[R - 1] += x
if L & 1:
self.lazy[L - 1] += x; self.data[L - 1] += x
L += 1
L >>= 1; R >>= 1
for i in ids:
self.data[i - 1] = self.calc(self.data[2 * i - 1], self.data[2 * i])
def query(self, l, r):
self.propagates(*self.gindex(l, r + 1))
L = self.N0 + l; R = self.N0 + r + 1
s = self.initVal
while L < R:
if R & 1:
R -= 1
s = self.calc(s, self.data[R - 1])
if L & 1:
s = self.calc(s, self.data[L - 1])
L += 1
L >>= 1; R >>= 1
return s
#
def main():
N = int(input())
A = getlist()
for i in range(N):
if A[i] > i + 1:
print("No")
return
lSeg = lazySegTree(N + 1)
lSeg.initialize([0] + A)
for i in range(N, 0, -1):
val = lSeg.query(i, i)
if val % i != 0:
print("No")
return
x = int(val // i)
lSeg.update(0, i - 1, x)
print("Yes")
if __name__ == '__main__':
main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0