結果
問題 | 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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 44 ms
59,520 KB |
testcase_01 | AC | 40 ms
53,632 KB |
testcase_02 | AC | 233 ms
78,464 KB |
testcase_03 | AC | 247 ms
78,452 KB |
testcase_04 | AC | 231 ms
78,276 KB |
testcase_05 | AC | 230 ms
78,136 KB |
testcase_06 | AC | 243 ms
78,720 KB |
testcase_07 | AC | 238 ms
77,992 KB |
testcase_08 | TLE | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
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 | -- | - |
ソースコード
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)