結果

問題 No.2901 Logical Sum of Substring
コンテスト
ユーザー None
提出日時 2024-05-12 02:31:36
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,493 bytes
コンパイル時間 360 ms
コンパイル使用メモリ 82,340 KB
実行使用メモリ 165,184 KB
最終ジャッジ日時 2024-09-20 20:50:56
合計ジャッジ時間 6,754 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 6 TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

def merge(total, Ai):
    res=total[:]
    for p in range(K):
        res[p] += Ai[p]
    return res


def inv_merge(total, Ai):
    res = total[:]
    for p in range(K):
        res[p] -= Ai[p]
    return res

def is_impossible(total):
    return any(v <= 0 for v in total)


def get_sum(l,r):
    """
    [l,r)
    Lidx = [bitが変化するタイミング1, タイミング2,...]
    Lcnt = [[bit0の個数, bit1の個数, ...], ]
    """

    kl=l//d # lにいるブロック番号
    kr=r//d # rのいるブロック番号
    if kl==kr:
        Ridx=list(range(l,r))
        Rcnt = []
        for i in range(l,r):
            cnt = [0] * K
            for p in range(K):
                if (A[i] >> p) & 1 == 1:
                    cnt[p] += 1
            Rcnt.append(cnt[:])
        Lidx=list(range(l,r))
        Lcnt = []
        for i in range(l,r)[::-1]:
            cnt = [0] * K
            for p in range(K):
                if (A[i] >> p) & 1 == 1:
                    cnt[p] += 1
            Lcnt.append(cnt[:])
        Lcnt.reverse()
    else:
        Ridx=list(range(l,(kl+1)*d))
        for k in range(kl+1,kr):
            Ridx+=R[k][0]
        Ridx+=list(range(kr*d,r))

        Rcnt=[]
        for i in range(l,(kl+1)*d):
            cnt = [0] * K
            for p in range(K):
                if (A[i]>>p)&1==1:
                    cnt[p]+=1
            Rcnt.append(cnt[:])
        for k in range(kl+1,kr):
            Rcnt+=R[k][1]
        for i in range(kr*d,r):
            cnt = [0] * K
            for p in range(K):
                if (A[i]>>p)&1==1:
                    cnt[p]+=1
            Rcnt.append(cnt[:])

        Lidx=list(range(l,(kl+1)*d))
        for k in range(kl+1,kr):
            Lidx+=list(reversed(L[k][0]))
        Lidx+=list(range(kr*d,r))

        Lcnt=[]
        for i in range(kr*d,r)[::-1]:
            cnt = [0] * K
            for p in range(K):
                if (A[i]>>p)&1==1:
                    cnt[p]+=1
            Lcnt.append(cnt[:])
        for k in range(kl+1,kr)[::-1]:
            Lcnt+=L[k][1]
        for i in range(l,(kl+1)*d)[::-1]:
            cnt = [0] * K
            for p in range(K):
                if (A[i]>>p)&1==1:
                    cnt[p]+=1
            Lcnt.append(cnt[:])
        Lcnt.reverse()

    res = float("inf")
    right=0
    total = [0]*K
    for left in range(len(Lidx)):
        while right < len(Ridx) and is_impossible(total):
            total = merge(total, Rcnt[right])
            right += 1
        if is_impossible(total):
            break
        res = min(Ridx[right-1]+1 - Lidx[left], res)
        if Ridx[right-1]+1 == Lidx[left]:
            right += 1
        else:
            total = inv_merge(total, Lcnt[left])
    return res

def update(x,v):
    A[x]=v
    k=x//d
    R[k]=([],[])
    L[k]=([],[])
    total=0
    cnt=[0]*K
    for i in range(d*k,d*(k+1)):
        for p in range(K):
            if (A[i]>>p)&1==1:
                cnt[p]+=1
        if total|A[i]!=total:
            total|=A[i]
            R[k][0].append(i)
            R[k][1].append(cnt[:])
            cnt = [0] * K
    total=0
    cnt=[0]*K
    for i in range(d*k,d*(k+1))[::-1]:
        for p in range(K):
            if (A[i]>>p)&1==1:
                cnt[p]+=1
        if total|A[i]!=total:
            total|=A[i]
            L[k][0].append(i)
            L[k][1].append(cnt[:])
            cnt = [0] * K


N,K=map(int, input().split())
A=list(map(int, input().split()))
Q=int(input())

N2=100 # number of buckets
d=(N+N2-1)//N2 # bucket size
A=A+[0]*(d*N2-N)
R=[([],[]) for _ in range(N2)] # (増えるタイミング, 増えるbitの個数)
L=[([],[]) for _ in range(N2)]

for k in range(N2):
    total=0
    cnt=[0]*K
    for i in range(d*k,d*(k+1)):
        for p in range(K):
            if (A[i]>>p)&1==1:
                cnt[p]+=1
        if total|A[i]!=total:
            total|=A[i]
            R[k][0].append(i)
            R[k][1].append(cnt[:])
            cnt = [0] * K
    total=0
    cnt=[0]*K
    for i in range(d*k,d*(k+1))[::-1]:
        for p in range(K):
            if (A[i]>>p)&1==1:
                cnt[p]+=1
        if total|A[i]!=total:
            total|=A[i]
            L[k][0].append(i)
            L[k][1].append(cnt[:])
            cnt = [0] * K




for _ in range(Q):
    q=list(map(int, input().split()))
    if q[0]==1:
        x,v=q[1:]
        update(x-1,v)
    else:
        l,r=q[1:]
        res=get_sum(l-1,r)
        print(res if res!=float("inf") else -1)
0