#766918 (PyPy3) No.1036 Make One With GCD 2

• 問題: No.1036 Make One With GCD 2
• ユーザー: terasa
• 提出日時: 2022-05-28 18:34:53
• 言語: PyPy3 (7.3.15)
• 結果: WA
• 実行時間: -
• コード長: 2,657 bytes
• コンパイル時間: 282 ms
• コンパイル使用メモリ: 82,560 KB
• 実行使用メモリ: 230,040 KB
• 最終ジャッジ日時: 2024-09-20 23:26:46
• 合計ジャッジ時間: 24,311 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

ファイルパターン	結果
sample	AC * 3 WA * 1
other	AC * 16 WA * 25

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
import sys
import pypyjit
import itertools
import heapq
import math
from collections import deque, defaultdict, Counter
import bisect
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
pypyjit.set_param('max_unroll_recursion=-1')
def index_lt(a, x):
    'return largest index s.t. A[i] < x or -1 if it does not exist'
    return bisect.bisect_left(a, x) - 1
def index_le(a, x):
    'return largest index s.t. A[i] <= x or -1 if it does not exist'
    return bisect.bisect_right(a, x) - 1
def index_gt(a, x):
    'return smallest index s.t. A[i] > x or len(a) if it does not exist'
    return bisect.bisect_right(a, x)
def index_ge(a, x):
    'return smallest index s.t. A[i] >= x or len(a) if it does not exist'
    return bisect.bisect_left(a, x)
class SegTree:
    def __init__(self, N, func, e):
        self.N = N
        self.func = func
        self.X = [e] * (N << 1)
        self.e = e
    def build(self, seq):
        for i in range(self.N):
            self.X[self.N + i] = seq[i]
        for i in range(self.N)[::-1]:
            self.X[i] = self.func(self.X[i << 1], self.X[i << 1 | 1])
    def add(self, i, x):
        i += self.N
        self.X[i] += x
        while i > 1:
            i >>= 1
            self.X[i] = self.func(self.X[i << 1], self.X[i << 1 | 1])
    def update(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.func(self.X[i << 1], self.X[i << 1 | 1])
    def query(self, L, R):
        L += self.N
        R += self.N
        vL = self.X[L]
        vR = self.X[R - 1]
        while L < R:
            if L & 1:
                vL = self.func(vL, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.func(self.X[R], vR)
            L >>= 1
            R >>= 1
        return self.func(vL, vR)
N = int(input())
A = list(map(int, input().split()))
B = []
tmp = []
cnt1 = 0
for a in A:
    if a == 1:
        cnt1 += 1
        if len(tmp) > 0:
            B.append(tmp)
            tmp = []
    else:
        tmp.append(a)
if len(tmp) > 0:
    B.append(tmp)
ans = (1 + N) * N // 2 - (N - cnt1)
for b in B:
    st = SegTree(len(b), math.gcd, 1)
    st.build(b)
    def solve(b):
        global ans
        l = 0
        r = 1
        while r <= len(b):
            while st.query(l, r) > 1:
                r += 1
                if r > len(b):
                    return
            d = r - l - 1
            ans -= d * (d - 1) // 2
            while st.query(l, r) == 1:
                l += 1
        d = r - l - 1
        ans -= d * (d - 1) // 2
    solve(b)
print(ans)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX