結果

問題 No.3763 Compress Pancakes
コンテスト
ユーザー kidodesu
提出日時 2026-10-09 23:59:57
言語 PyPy3
(7.3.23 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 2,585 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 64 ms
コンパイル使用メモリ 82,888 KB
実行使用メモリ 339,568 KB
最終ジャッジ日時 2026-10-10 00:00:35
合計ジャッジ時間 34,033 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 21 WA * 1 TLE * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from atcoder.segtree import SegTree
from atcoder.lazysegtree import LazySegTree
def main():
    n, q = list(map(int, input().split()))
    A = list(map(int, input().split()))
    D = set([1])
    c = 1
    while c <= 10**18:
        D.add(c)
        c *= 2
    
    def op0(a, b):
        if a == -1:
            return b
        if b == -1:
            return a
        if min(a, b) == -2:
            return -2
        if a != b:
            return -2
        return a

    def op1(a, b):
        if a[0] == -1:
            return b
        if b[0] == -1:
            return a
        if a[2] != b[2] or min(a[2], b[2]) == -2:
            return (-2, -2, -2, -2)
        if max(a[0], b[0]) == a[0] | b[0]:
            if a[1] < b[1]:
                return max(a[0], b[0]), max(a[1], b[1]), a[2], b[3]
            else:
                return max(a[0], b[0]), max(a[1], b[1]), a[2], a[3]
        return (-2, -2, -2, -2)
    
    def mapp(a, b):
        if b[2] < 0:
            return b
        return (((b[3]+a)//b[2])%b[1], b[1], b[2], b[3]+a)
    def comp(a, b):
        return a+b
    
    def make(a):
        c = 1
        while not a % 2:
            a //= 2
            c *= 2
        return a, c
    B = [0]
    X = []
    for a in A:
        B.append(a+B[-1])
    for i in range(n):
        a = A[i]
        b = B[i]
        a, c = make(a)
        X.append(((b//a)%c, c, a, b))
    
    #st0 = SegTree(lambda a, b: op0, -1, [make(a)[0] for a in A])
    st1 = LazySegTree(op1, (-1, -1, -1, -1), mapp, comp, 0, X)
    st2 = SegTree(lambda a, b: a+b, 0, A)
    idx = 0
    for _ in range(q):
        Q = list(map(int, input().split()))
        if Q[0] == 1:
            k, x = Q[1:]
            k -= 1
            d = x-A[k]
            A[k] = x
            st2.set(k, x)
            rep = st2.prod(0, k)
            a, c = make(x)
            st1.set(k, ((rep//a)%c, c, a, rep))
            st1.apply(k+1, n, d)
        else:
            idx += 1
            l, r = Q[1:]
            l -= 1
            rep = st1.prod(l, r)
            #print([st1.get(i) for i in range(n)])
            #print(A)
            #print(rep)
            #print(l, r)
            #print(st1.prod(0, 2))
            #print(op1(st1.get(0), st1.get(1)))
            #print(st2.prod(0, l))
            rep2 = st2.prod(l, r)
            if rep[2] == -2:
                print("No")
            elif st2.prod(0, l) // rep[2] % rep[1] == rep[0] and rep2 // rep[2] in D:
                print("Yes")
            else:
                print("No")
            #print("Yes" if rep[2] != -2 else "No")

main()
0