結果
問題 | No.318 学学学学学 |
ユーザー |
![]() |
提出日時 | 2020-06-15 23:20:37 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 518 ms / 2,000 ms |
コード長 | 1,446 bytes |
コンパイル時間 | 163 ms |
コンパイル使用メモリ | 82,404 KB |
実行使用メモリ | 120,040 KB |
最終ジャッジ日時 | 2024-07-03 11:36:37 |
合計ジャッジ時間 | 8,652 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
import sys,heapqinput = sys.stdin.buffer.readlinen=int(input())A=[int(i) for i in input().split()]LV=(n-1).bit_length()N0=2**LVdata=[0]*(2*N0)lazy=[None]*(2*N0)# 伝搬対象の区間を求める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 simport collectionsDL=collections.defaultdict(int)DR=collections.defaultdict(int)for i,a in enumerate(A):if DL[a]==0:DL[a]=i+1DR[a]=i+1AA=sorted(list(set(A)))for a in AA:update(DL[a]-1,DR[a],a)B=[]for i in range(n):B.append(query(i,i+1))print(*B)