結果

問題 No.1036 Make One With GCD 2
ユーザー 草苺奶昔草苺奶昔
提出日時 2023-03-10 18:28:13
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 810 ms / 2,000 ms
コード長 2,283 bytes
コンパイル時間 440 ms
コンパイル使用メモリ 81,280 KB
実行使用メモリ 252,408 KB
最終ジャッジ日時 2023-10-18 06:45:53
合計ジャッジ時間 24,167 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 374 ms
176,888 KB
testcase_01 AC 255 ms
157,948 KB
testcase_02 AC 413 ms
249,948 KB
testcase_03 AC 108 ms
96,524 KB
testcase_04 AC 127 ms
119,104 KB
testcase_05 AC 64 ms
65,808 KB
testcase_06 AC 63 ms
65,824 KB
testcase_07 AC 169 ms
110,636 KB
testcase_08 AC 152 ms
103,856 KB
testcase_09 AC 639 ms
161,808 KB
testcase_10 AC 606 ms
148,668 KB
testcase_11 AC 470 ms
161,960 KB
testcase_12 AC 427 ms
148,744 KB
testcase_13 AC 624 ms
158,940 KB
testcase_14 AC 674 ms
163,824 KB
testcase_15 AC 788 ms
182,904 KB
testcase_16 AC 626 ms
183,816 KB
testcase_17 AC 810 ms
186,156 KB
testcase_18 AC 79 ms
73,956 KB
testcase_19 AC 78 ms
74,120 KB
testcase_20 AC 79 ms
74,604 KB
testcase_21 AC 79 ms
74,516 KB
testcase_22 AC 772 ms
182,328 KB
testcase_23 AC 611 ms
141,344 KB
testcase_24 AC 620 ms
185,532 KB
testcase_25 AC 590 ms
170,996 KB
testcase_26 AC 758 ms
180,708 KB
testcase_27 AC 63 ms
65,808 KB
testcase_28 AC 62 ms
65,812 KB
testcase_29 AC 62 ms
65,816 KB
testcase_30 AC 62 ms
65,844 KB
testcase_31 AC 62 ms
66,532 KB
testcase_32 AC 62 ms
66,840 KB
testcase_33 AC 61 ms
65,904 KB
testcase_34 AC 64 ms
66,628 KB
testcase_35 AC 61 ms
65,820 KB
testcase_36 AC 63 ms
65,844 KB
testcase_37 AC 61 ms
65,836 KB
testcase_38 AC 382 ms
252,408 KB
testcase_39 AC 345 ms
173,220 KB
testcase_40 AC 482 ms
140,796 KB
testcase_41 AC 406 ms
173,232 KB
testcase_42 AC 391 ms
173,228 KB
testcase_43 AC 446 ms
215,060 KB
testcase_44 AC 399 ms
182,484 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from math import gcd
from typing import Callable, Generic, List, TypeVar


E = TypeVar("E")


class SlidingWindowAggregation(Generic[E]):
    """SlidingWindowAggregation

    Api:
    1. append value to tail,O(1).
    2. pop value from head,O(1).
    3. query aggregated value in window,O(1).
    """

    __slots__ = ["_stack0", "_stack1", "_stack2", "_stack3", "_e0", "_e1", "_size", "_op", "_e"]

    def __init__(self, e: Callable[[], E], op: Callable[[E, E], E]):
        """
        Args:
            e: unit element
            op: merge function
        """
        self._stack0 = []
        self._stack1 = []
        self._stack2 = []
        self._stack3 = []
        self._e = e
        self._e0 = e()
        self._e1 = e()
        self._size = 0
        self._op = op

    def append(self, value: E) -> None:
        if not self._stack0:
            self._push0(value)
            self._transfer()
        else:
            self._push1(value)
        self._size += 1

    def popleft(self) -> None:
        if not self._size:
            return
        if not self._stack0:
            self._transfer()
        self._stack0.pop()
        self._stack2.pop()
        self._e0 = self._stack2[-1] if self._stack2 else self._e()
        self._size -= 1

    def query(self) -> E:
        return self._op(self._e0, self._e1)

    def _push0(self, value):
        self._stack0.append(value)
        self._e0 = self._op(value, self._e0)
        self._stack2.append(self._e0)

    def _push1(self, value):
        self._stack1.append(value)
        self._e1 = self._op(self._e1, value)
        self._stack3.append(self._e1)

    def _transfer(self):
        while self._stack1:
            self._push0(self._stack1.pop())
        while self._stack3:
            self._stack3.pop()
        self._e1 = self._e()

    @property
    def size(self):
        return self._size




if __name__ == "__main__":
    n = int(input())
    nums = list(map(int, input().split()))
    S = SlidingWindowAggregation(lambda: 0, gcd)
    res = 0
    right = 0
    for left in range(n):
        right = max(right, left)
        while right < n and gcd(S.query(), nums[right]) != 1:
            S.append(nums[right])
            right += 1
        res += n - right
        S.popleft()
    print(res)
0