結果
問題 | No.318 学学学学学 |
ユーザー |
![]() |
提出日時 | 2020-12-15 13:35:37 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 685 ms / 2,000 ms |
コード長 | 1,583 bytes |
コンパイル時間 | 175 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 112,492 KB |
最終ジャッジ日時 | 2024-09-20 01:38:39 |
合計ジャッジ時間 | 10,746 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
def gindex(l, r):L = (l + N0) >> 1; R = (r + N0) >> 1lc = 0 if l & 1 else (L & -L).bit_length()rc = 0 if r & 1 else (R & -R).bit_length()for i in range(LV):if rc <= i:yield Rif L < R and lc <= i:yield LL >>= 1; R >>= 1# 遅延伝搬処理def propagates(*ids):for i in reversed(ids):v = lazy[i-1]if v is None:continuelazy[2*i-1] = lazy[2*i] = data[2*i-1] = data[2*i] = v >> 1lazy[i-1] = None# 区間[l, r)をxに更新def update(l, r, x):*ids, = gindex(l, r)propagates(*ids)L = N0 + l; R = N0 + rv = xwhile L < R:if R & 1:R -= 1lazy[R-1] = data[R-1] = vif L & 1:lazy[L-1] = data[L-1] = vL += 1L >>= 1; R >>= 1; v <<= 1for i in ids:data[i-1] = data[2*i-1] + data[2*i]# 区間[l, r)内の合計を求めるdef query(l, r):propagates(*gindex(l, r))L = N0 + l; R = N0 + rs = 0while L < R:if R & 1:R -= 1s += data[R-1]if L & 1:s += data[L-1]L += 1L >>= 1; R >>= 1return sN=int(input())n=NA=list(map(int, input().split()))D={}for i in range(N):if A[i] not in D:D[A[i]]=[i,i]else:D[A[i]][-1]=iD=sorted(D.items())# N: 処理する区間の長さLV=(N-1).bit_length()N0=2**LVdata=[0]*(2*N0)lazy=[None]*(2*N0)for a,b in D:update(b[0],b[1]+1,a)F=[]for i in range(N):F.append(query(i,i+1))print(*F)