結果
問題 | No.1036 Make One With GCD 2 |
ユーザー |
![]() |
提出日時 | 2024-01-15 12:12:23 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,400 ms / 2,000 ms |
コード長 | 3,570 bytes |
コンパイル時間 | 378 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 200,028 KB |
最終ジャッジ日時 | 2024-09-28 02:15:18 |
合計ジャッジ時間 | 25,219 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
ソースコード
class SegmentTree:def __init__(self,n,identity_e,combine_f,):self._n = nself._size = 1while self._size < self._n:self._size <<= 1self._identity_e = identity_eself._combine_f = combine_fself._node = [self._identity_e] * (2 * self._size)def build(self, array):assert len(array) == self._nfor index, value in enumerate(array, start=self._size):self._node[index] = valuefor index in range(self._size - 1, 0, -1):self._node[index] = self._combine_f(self._node[index << 1 | 0],self._node[index << 1 | 1])def update(self, index, value):i = self._size + indexself._node[i] = valuewhile i > 1:i >>= 1self._node[i] = self._combine_f(self._node[i << 1 | 0],self._node[i << 1 | 1])def fold(self, L, R):L += self._sizeR += self._sizevalue_L = self._identity_evalue_R = self._identity_ewhile L < R:if L & 1:value_L = self._combine_f(value_L, self._node[L])L += 1if R & 1:R -= 1value_R = self._combine_f(self._node[R], value_R)L >>= 1R >>= 1return self._combine_f(value_L, value_R)def get(self, p):return self._node[p + self._size]def max_right(self, l, f):assert 0 <= l <= self._nassert f(self._identity_e)if l == self._n:return self._nl += self._sizesm = self._identity_ewhile True:while l % 2 == 0:l >>= 1if not f(self._combine_f(sm, self._node[l])):while l < self._size:l <<= 1if f(self._combine_f(sm, self._node[l])):sm = self._combine_f(sm, self._node[l])l += 1return l - self._sizesm = self._combine_f(sm, self._node[l])l += 1if l & -l == l:breakreturn self._ndef min_left(self, r, f):assert 0 <= r <= self._nassert f(self._identity_e)if r == 0:return 0r += self._sizesm = self._identity_ewhile True:r -= 1while r > 1 and r % 2:r >>= 1if not f(self._combine_f(self._node[r], sm)):while r < self._size:r = 2 * r + 1if f(self._combine_f(self._node[r], sm)):sm = self._combine_f(self._node[r], sm)r -= 1return r + 1 - self._sizesm = self._combine_f(self._node[r], sm)if r & -r == r:breakreturn 0from math import gcdN = int(input())A = list(map(int, input().split()))T = SegmentTree(N, 0, gcd)T.build(A)ans = N * (N + 1) // 2def f(x):return x != 1for i in range(N):ans -= i+1 - T.min_left(i+1, f)# if T.fold(i, N) != 1:# ans -= N - i# continue# yes = i# no = N# while no - yes != 1:# mid = (yes + no) // 2# if T.fold(i, mid) != 1:# yes = mid# else:# no = mid# ans -= yes - iprint(ans)