結果

問題 No.2901 Logical Sum of Substring
ユーザー NoneNone
提出日時 2024-05-12 13:38:31
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 5,296 bytes
コンパイル時間 483 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 222,156 KB
最終ジャッジ日時 2024-09-20 20:51:19
合計ジャッジ時間 16,692 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 87 ms
82,176 KB
testcase_01 AC 83 ms
76,544 KB
testcase_02 AC 261 ms
79,064 KB
testcase_03 AC 267 ms
78,772 KB
testcase_04 AC 254 ms
79,320 KB
testcase_05 AC 261 ms
79,076 KB
testcase_06 AC 271 ms
78,788 KB
testcase_07 AC 261 ms
79,028 KB
testcase_08 TLE -
testcase_09 TLE -
testcase_10 TLE -
testcase_11 TLE -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
権限があれば一括ダウンロードができます

ソースコード

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:
        res=float("inf")

        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:
        res=float("inf")
        for k in range(kl+1,kr):
            res=min(X[k], res)

        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()

    right=0
    total = [0]*K
    for left in range(len(Lidx)):
        while right < len(Ridx) and (is_impossible(total) or ((Ridx[right-1])//d<=Lidx[left]//d and kl+1<=Lidx[left]//d<kr)  ):
            total = merge(total, Rcnt[right])
            right += 1
        if is_impossible(total):
            break
        res = min(Ridx[right-1]+1 - Lidx[left], res)
        total = inv_merge(total, Lcnt[left])
    return res


def eval_bucket(k):
    res = float("inf")
    total = [0] * K
    C = [[] for _ in range(d)]

    for i in range(d):
        cnt = [0] * K
        for p in range(K):
            if (A[d * k + i] >> p) & 1 == 1:
                cnt[p] += 1
        C[i] = cnt[:]

    right = 0
    for left in range(d):
        while right < d and is_impossible(total):
            total = merge(total, C[right])
            right += 1

        if is_impossible(total):
            break
        res = min(right - left, res)
        if right == left:
            right += 1
        else:
            total = inv_merge(total, C[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

    X[k]=eval_bucket(k)







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

N2=1000 # number of buckets
d=(N+N2-1)//N2 # bucket size
A=A+[0]*(d*N2-N)
X=[0]*N2 # bucket内全体の答え
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
    X[k]=eval_bucket(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