結果

問題 No.1036 Make One With GCD 2
コンテスト
ユーザー None
提出日時 2021-03-26 00:10:45
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 791 ms / 2,000 ms
コード長 5,288 bytes
コンパイル時間 330 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 191,944 KB
最終ジャッジ日時 2024-09-16 14:36:20
合計ジャッジ時間 19,196 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

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