結果
問題 | No.318 学学学学学 |
ユーザー | takakin |
提出日時 | 2020-06-15 23:20:37 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 626 ms / 2,000 ms |
コード長 | 1,446 bytes |
コンパイル時間 | 264 ms |
コンパイル使用メモリ | 87,032 KB |
実行使用メモリ | 134,608 KB |
最終ジャッジ日時 | 2023-09-16 10:37:40 |
合計ジャッジ時間 | 11,263 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 177 ms
80,268 KB |
testcase_01 | AC | 210 ms
86,260 KB |
testcase_02 | AC | 229 ms
88,372 KB |
testcase_03 | AC | 202 ms
84,644 KB |
testcase_04 | AC | 224 ms
87,036 KB |
testcase_05 | AC | 620 ms
134,608 KB |
testcase_06 | AC | 599 ms
109,972 KB |
testcase_07 | AC | 510 ms
103,344 KB |
testcase_08 | AC | 434 ms
100,128 KB |
testcase_09 | AC | 371 ms
97,956 KB |
testcase_10 | AC | 301 ms
95,824 KB |
testcase_11 | AC | 626 ms
134,508 KB |
testcase_12 | AC | 493 ms
109,656 KB |
testcase_13 | AC | 447 ms
100,896 KB |
testcase_14 | AC | 400 ms
98,492 KB |
testcase_15 | AC | 361 ms
97,464 KB |
testcase_16 | AC | 303 ms
95,780 KB |
testcase_17 | AC | 433 ms
108,084 KB |
testcase_18 | AC | 401 ms
107,872 KB |
testcase_19 | AC | 438 ms
108,172 KB |
testcase_20 | AC | 316 ms
94,212 KB |
testcase_21 | AC | 88 ms
71,584 KB |
testcase_22 | AC | 88 ms
71,708 KB |
testcase_23 | AC | 88 ms
71,492 KB |
testcase_24 | AC | 88 ms
71,668 KB |
testcase_25 | AC | 87 ms
71,748 KB |
testcase_26 | AC | 88 ms
71,464 KB |
testcase_27 | AC | 89 ms
71,772 KB |
testcase_28 | AC | 90 ms
71,588 KB |
ソースコード
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)