結果
問題 | 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,heapq input = sys.stdin.buffer.readline n=int(input()) A=[int(i) for i in input().split()] LV=(n-1).bit_length() N0=2**LV data=[0]*(2*N0) lazy=[None]*(2*N0) # 伝搬対象の区間を求める def gindex(l, r): L=(l + N0)>>1; R = (r+N0) >> 1 lc=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 R if L<R and lc<=i: yield L L>>=1; R>>=1 # 遅延伝搬処理 def propagates(*ids): for i in reversed(ids): v=lazy[i-1] if v is None: continue lazy[2*i-1]=lazy[2*i]=data[2*i-1]=data[2*i]=v>>1 lazy[i-1]=None # 区間[l, r)をxに更新 def update(l, r, x): *ids,=gindex(l, r) propagates(*ids) L=N0+l; R=N0+r v=x while L<R: if R&1: R-=1 lazy[R-1]=data[R-1]=v if L & 1: lazy[L-1]=data[L-1]=v L+=1 L>>=1; R>>=1; v<<=1 for 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+r s=0 while L<R: if R&1: R-=1 s+=data[R-1] if L&1: s+=data[L-1] L+=1 L>>=1; R>>=1 return s import collections DL=collections.defaultdict(int) DR=collections.defaultdict(int) for i,a in enumerate(A): if DL[a]==0: DL[a]=i+1 DR[a]=i+1 AA=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)