結果

問題 No.3763 Compress Pancakes
コンテスト
ユーザー ei1333333
提出日時 2026-10-04 19:56:07
言語 PyPy3
(7.3.23 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 997 ms / 2,000 ms
+ 692µs
コード長 2,408 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 687 ms
コンパイル使用メモリ 81,732 KB
実行使用メモリ 258,136 KB
最終ジャッジ日時 2026-10-09 20:53:16
合計ジャッジ時間 13,969 ms
ジャッジサーバーID
（参考情報） 		judge5_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

input = sys.stdin.readline


# S = (sum, mx, pos, odd, ok)

E = (0, 0, 0, 0, True)


def make_s(x):
    w = x & -x
    return (w, w, 0, x // w, True)


def op(a, b):
    asum, amx, apos, aodd, aok = a
    bsum, bmx, bpos, bodd, bok = b

    if asum == 0:
        return b
    if bsum == 0:
        return a

    s = asum + bsum
    odd = aodd if aodd == bodd else -1

    d = asum + bpos - apos
    ok = aok and bok and d % min(amx, bmx) == 0

    if amx >= bmx:
        mx = amx
        pos = apos
    else:
        mx = bmx
        pos = asum + bpos

    return (s, mx, pos, odd, ok)


def is_power_of_two(x):
    return x > 0 and (x & (x - 1)) == 0


def can_merge(a):
    s, mx, pos, odd, ok = a
    return (
        odd > 0
        and ok
        and pos % mx == 0
        and is_power_of_two(s)
    )


class SegTree:
    def __init__(self, a):
        n = len(a)
        size = 1
        while size < n:
            size <<= 1

        self.size = size
        self.dat = [E] * (2 * size)

        for i, x in enumerate(a):
            self.dat[size + i] = x

        for i in range(size - 1, 0, -1):
            self.dat[i] = op(self.dat[i << 1],
                             self.dat[i << 1 | 1])

    def set(self, p, x):
        p += self.size
        self.dat[p] = x

        while p > 1:
            p >>= 1
            self.dat[p] = op(
                self.dat[p << 1],
                self.dat[p << 1 | 1]
            )

    # [l, r)
    def prod(self, l, r):
        l += self.size
        r += self.size

        sml = E
        smr = E

        while l < r:
            if l & 1:
                sml = op(sml, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                smr = op(self.dat[r], smr)

            l >>= 1
            r >>= 1

        return op(sml, smr)


def main():
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))

    seg = SegTree([make_s(x) for x in A])

    ans = []

    for _ in range(Q):
        query = list(map(int, input().split()))

        if query[0] == 1:
            _, k, x = query
            seg.set(k - 1, make_s(x))

        else:
            _, l, r = query
            s = seg.prod(l - 1, r)

            if can_merge(s):
                ans.append("Yes")
            else:
                ans.append("No")

    print("\n".join(ans))


if __name__ == "__main__":
    main()
0