結果
問題 | 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 |
ソースコード
import sys; input = sys.stdin.buffer.readlinesys.setrecursionlimit(10**7)from collections import defaultdictcon = 10 ** 9 + 7; INF = float("inf")def getlist():return list(map(int, input().split()))class lazySegTree(object):def __init__(self, N):self.N = Nself.LV = (N - 1).bit_length()self.N0 = 2 ** self.LVself.initVal = 0self.data = [0] * (2 * self.N0)self.lazy = [0] * (2 * self.N0)def calc(self, a, b):return a + bdef 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) >> 1lc = 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 Rif L < R and lc <= i:yield LL >>= 1; R >>= 1def propagates(self, *ids):for i in reversed(ids):v = self.lazy[i - 1]if not v:continueself.lazy[2 * i - 1] += v; self.lazy[2 * i] += vself.data[2 * i - 1] += v; self.data[2 * i] += vself.lazy[i - 1] = 0def update(self, l, r, x):*ids, = self.gindex(l, r + 1)self.propagates(*ids)L = self.N0 + l; R = self.N0 + r + 1while L < R:if R & 1:R -= 1self.lazy[R - 1] += x; self.data[R - 1] += xif L & 1:self.lazy[L - 1] += x; self.data[L - 1] += xL += 1L >>= 1; R >>= 1for 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 + 1s = self.initValwhile L < R:if R & 1:R -= 1s = self.calc(s, self.data[R - 1])if L & 1:s = self.calc(s, self.data[L - 1])L += 1L >>= 1; R >>= 1return s#処理内容def main():N = int(input())A = getlist()for i in range(N):if A[i] > i + 1:print("No")returnlSeg = 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")returnx = int(val // i)lSeg.update(0, i - 1, x)print("Yes")if __name__ == '__main__':main()