結果

問題 No.1036 Make One With GCD 2
ユーザー rlangevinrlangevin
提出日時 2024-01-15 08:58:10
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,514 bytes
コンパイル時間 262 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 290,200 KB
最終ジャッジ日時 2024-09-28 02:12:18
合計ジャッジ時間 11,140 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample -- * 4
other TLE * 1 -- * 40
権限があれば一括ダウンロードができます

ソースコード

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

class SegmentTree:
def __init__(self,
n,
identity_e,
combine_f,
):
self._n = n
self._size = 1
while self._size < self._n:
self._size <<= 1
self._identity_e = identity_e
self._combine_f = combine_f
self._node = [self._identity_e] * (2 * self._size)
def build(self, array):
assert len(array) == self._n
for index, value in enumerate(array, start=self._size):
self._node[index] = value
for 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 + index
self._node[i] = value
while i > 1:
i >>= 1
self._node[i] = self._combine_f(
self._node[i << 1 | 0],
self._node[i << 1 | 1]
)
def fold(self, L, R):
L += self._size
R += self._size
value_L = self._identity_e
value_R = self._identity_e
while L < R:
if L & 1:
value_L = self._combine_f(value_L, self._node[L])
L += 1
if R & 1:
R -= 1
value_R = self._combine_f(self._node[R], value_R)
L >>= 1
R >>= 1
return 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._n
assert f(self._identity_e)
if l == self._n:
return self._n
l += self._size
sm = self._identity_e
while True:
while l % 2 == 0:
l >>= 1
if not f(self._combine_f(sm, self._node[l])):
while l < self._size:
l <<= 1
if f(self._combine_f(sm, self._node[l])):
sm = self._combine_f(sm, self._node[l])
return l - self._size
sm = self._combine_f(sm, self._node[l])
l += 1
if l & -l == l:
break
return self._n
def min_left(self, r, f):
assert 0 <= r <= self._n
assert f(self._identity_e)
if r == 0:
return 0
r += self._size
sm = self._identity_e
while True:
r -= 1
while r > 1 and r % 2:
r >>= 1
if not f(self._combine_f(self._node[r], sm)):
while r < self._size:
r = 2 * r + 1
if f(self._combine_f(self._node[r], sm)):
sm = self._combine_f(self._node[r], sm)
r -= 1
return r + 1 - self._size
sm = self._combine_f(self._node[r], sm)
if r & -r == r:
break
return 0
from math import gcd
N = int(input())
A = list(map(int, input().split()))
T = SegmentTree(N, 0, gcd)
T.build(A)
ans = N * (N + 1) // 2
def f(x):
return x != 1
for i in range(N):
# ans -= T.max_right(i, f) - i
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 - i
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0