結果

問題 No.1036 Make One With GCD 2
ユーザー NoneNone
提出日時 2021-03-26 00:10:45
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 818 ms / 2,000 ms
コード長 5,288 bytes
コンパイル時間 552 ms
コンパイル使用メモリ 86,844 KB
実行使用メモリ 195,164 KB
最終ジャッジ日時 2023-10-14 20:45:05
合計ジャッジ時間 22,544 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 657 ms
191,928 KB
testcase_01 AC 368 ms
156,332 KB
testcase_02 AC 470 ms
152,784 KB
testcase_03 AC 139 ms
104,712 KB
testcase_04 AC 187 ms
120,688 KB
testcase_05 AC 74 ms
71,088 KB
testcase_06 AC 72 ms
71,068 KB
testcase_07 AC 211 ms
113,484 KB
testcase_08 AC 197 ms
102,380 KB
testcase_09 AC 503 ms
155,140 KB
testcase_10 AC 506 ms
172,340 KB
testcase_11 AC 519 ms
155,876 KB
testcase_12 AC 483 ms
172,952 KB
testcase_13 AC 710 ms
182,428 KB
testcase_14 AC 696 ms
191,056 KB
testcase_15 AC 648 ms
178,744 KB
testcase_16 AC 625 ms
179,672 KB
testcase_17 AC 645 ms
181,392 KB
testcase_18 AC 90 ms
76,776 KB
testcase_19 AC 99 ms
77,580 KB
testcase_20 AC 99 ms
77,516 KB
testcase_21 AC 96 ms
77,636 KB
testcase_22 AC 612 ms
177,528 KB
testcase_23 AC 507 ms
140,436 KB
testcase_24 AC 678 ms
180,720 KB
testcase_25 AC 605 ms
166,192 KB
testcase_26 AC 662 ms
175,844 KB
testcase_27 AC 72 ms
71,092 KB
testcase_28 AC 71 ms
70,884 KB
testcase_29 AC 71 ms
70,844 KB
testcase_30 AC 70 ms
70,712 KB
testcase_31 AC 70 ms
70,964 KB
testcase_32 AC 71 ms
74,940 KB
testcase_33 AC 71 ms
71,084 KB
testcase_34 AC 70 ms
71,020 KB
testcase_35 AC 70 ms
71,092 KB
testcase_36 AC 73 ms
71,064 KB
testcase_37 AC 72 ms
71,056 KB
testcase_38 AC 779 ms
194,792 KB
testcase_39 AC 530 ms
194,660 KB
testcase_40 AC 492 ms
139,536 KB
testcase_41 AC 704 ms
194,776 KB
testcase_42 AC 729 ms
194,852 KB
testcase_43 AC 751 ms
195,008 KB
testcase_44 AC 818 ms
195,164 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 


class SegmentTree:

    def __init__(self, n, op, e):
        self.n = n
        self.op = op
        self.e = e
        self.size = 1 << (self.n - 1).bit_length()      # st[self.size + i] = array[i]
        self.tree = [self.e] * (self.size << 1)

    def build(self, array):
        """bulid seg tree from array"""
        for i in range(self.n):
            self.tree[self.size + i] = array[i]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.op(self.tree[i<<1], self.tree[(i<<1)|1])

    def update(self, i, x):
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.op(self.tree[i<<1], self.tree[(i<<1)|1])

    def get_range(self, l, r):
        """
        get value from [l, r) (0-indexed)
        """
        l += self.size
        r += self.size
        res_l = self.e
        res_r = self.e
        while l < r:
            if l & 1:
                res_l = self.op(res_l, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                res_r = self.op(self.tree[r], res_r)
            l >>= 1
            r >>= 1
        return self.op(res_l, res_r)

    def get_all(self):
        return self.get_range(0,self.n)

    def max_right(self,l,func):
        """
        return r such that
            ・r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            ・r = n or f(op(a[l], a[l + 1], ..., a[r])) = false
        """
        if l == self.n: return self.n
        l += self.size
        sm = self.e
        while True:
            while l % 2 == 0: l >>= 1
            if not func(self.op(sm,self.tree[l])):
                while l < self.size:
                    l = 2 * l
                    if func(self.op(sm,self.tree[l])):
                        sm = self.op(sm, self.tree[l])
                        l += 1
                return l - self.size
            sm = self.op(sm, self.tree[l])
            l += 1
            if (l & -l) == l: break
        return self.n

    def min_left(self,r,func):
        """
        return l such that
            ・l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            ・l = 0 or f(op(a[l - 1], a[l], ..., a[r - 1])) = false
        """
        if r == 0: return 0
        r += self.size
        sm = self.e
        while True:
            r -= 1
            while r > 1 and (r % 2): r >>= 1
            if not func(self.op(self.tree[r],sm)):
                while r < self.size:
                    r = 2 * r + 1
                    if func(self.op(self.tree[r],sm)):
                        sm = self.op(self.tree[r], sm)
                        r -= 1
                return r + 1 - self.size
            sm = self.op(self.tree[r], sm)
            if (r & -r) == r: break
        return 0

    def __getitem__(self, i):
        if i<0: i=self.n+i
        return self.get_range(i,i+1)

    def __setitem__(self, i, value):
        if i<0: i=self.n+i
        self.update(i,value)

    def __iter__(self):
        for a in self.tree[self.size:self.size+self.n]:
            yield a

    def __str__(self):
        return str(self.tree[self.size:self.size+self.n])

class CompressSegment:
    """
    data = [(x0,A0),(x1,A1),(x2,A2),...]
    CS=CompressSegment(data)
    range: return compressed coordinate
        [xi,xj) -> [i, j)
    getitem[i]: return A[xi]
        i -> A[xi]
    """
    def __init__(self,data):
        data.sort(key=lambda x:x[0])
        self.X, self.A, self.Xc = [], [], dict()
        for i, (x,a) in enumerate(data):
            self.X.append(x)
            self.A.append(a)
            self.Xc[x]=i

    def __call__(self, l, r):
        return bisect_left(self.X,l), bisect_left(self.X,r)

    def range(self, l, r):
        return bisect_left(self.X,l), bisect_left(self.X,r)

    def __getitem__(self, i):
        return self.A[i]

    def __iter__(self):
        for a in self.A:
            yield a

def syakutori():

    total=0

    def is_possible_merge(l,r):
        return st.get_range(l,r)!=1

    def result(left,right,res):

        op="count"

        if op=="max_length":
            res=max(right-left,res)
        elif op=="min_length":
            res=min(right-left,res)
        elif op=="count":
            res+=(right-left)
        else:
            """ anything else """
        return res

    N=len(A)
    left, right, right_max=0,0,N
    res=0
    for left in range(right_max):
        while right<right_max and is_possible_merge(left,right+1):
            right+=1
        res = result(left,right,res)
        if right==left:
            right+=1
    return res

#############################################################
def example():
    global input
    example = iter(
        """
8
0 1 2 3 4 5 6 7
        """
            .strip().split("\n"))
    input = lambda: next(example)

#############################################################
import sys
from bisect import *
from math import gcd
input = sys.stdin.readline

# example()

N=int(input())
A=list(map(int, input().split()))

########## gcd ############################
# chain rule of op
def op(x,y):
    return gcd(x,y)
e = 0
st = SegmentTree(N, op, e)
###########################################

st.build(A)

res=syakutori()

print(N*(N+1)//2-res)
0