結果
問題 | No.1036 Make One With GCD 2 |
ユーザー |
![]() |
提出日時 | 2020-05-12 20:19:17 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,948 bytes |
コンパイル時間 | 285 ms |
コンパイル使用メモリ | 12,928 KB |
実行使用メモリ | 76,272 KB |
最終ジャッジ日時 | 2024-09-13 16:56:07 |
合計ジャッジ時間 | 11,570 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 4 |
other | TLE * 1 -- * 40 |
ソースコード
import sysinput=sys.stdin.readlineMOD=998244353N=int(input())A=list(map(int,input().split()))import math#####segfunc#####def segfunc(x, y):return math.gcd(x, y)######################ide_ele#####ide_ele = 0#################class LazySegmentTree:"""init(init_val, ide_ele): 配列init_valで初期化 O(N)update(l, r, x): 区間[l, r)をxに更新 O(logN)query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)"""def __init__(self, init_val, segfunc, ide_ele):"""init_val: 配列の初期値segfunc: 区間にしたい操作ide_ele: 単位元num: n以上の最小の2のべき乗data: 値配列(1-index)lazy: 遅延配列(1-index)"""n = len(init_val)self.segfunc = segfuncself.ide_ele = ide_eleself.num = 1 << (n - 1).bit_length()self.data = [ide_ele] * 2 * self.numself.lazy = [None] * 2 * self.num# 配列の値を葉にセットfor i in range(n):self.data[self.num + i] = init_val[i]# 構築していくfor i in range(self.num - 1, 0, -1):self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1])def gindex(self, l, r):"""伝搬する対象の区間を求めるlm: 伝搬する必要のある最大の左閉区間rm: 伝搬する必要のある最大の右開区間"""l += self.numr += self.numlm = l >> (l & -l).bit_length()rm = r >> (r & -r).bit_length()while r > l:if l <= lm:yield lif r <= rm:yield rr >>= 1l >>= 1while l:yield ll >>= 1def propagates(self, *ids):"""遅延伝搬処理ids: 伝搬する対象の区間"""for i in reversed(ids):v = self.lazy[i]if v is None:continueself.lazy[2*i]=self.lazy[2*i+1]=self.data[2*i]=self.data[2*i+1]=vself.lazy[i] = Nonedef query(self, l, r):"""[l, r)のsegfuncしたものを得るl: index(0-index)r: index(0-index)"""*ids, = self.gindex(l, r)self.propagates(*ids)res = self.ide_elel += self.numr += self.numwhile l < r:if l & 1:res = self.segfunc(res, self.data[l])l += 1if r & 1:res = self.segfunc(res, self.data[r - 1])l >>= 1r >>= 1return resLIS=LazySegmentTree(A,segfunc,ide_ele)cnt=0for i in range(N):for j in range(i,N+1):if LIS.query(i,j)!=1:cnt+=1print(cnt)