結果

問題 No.318 学学学学学
ユーザー takakin
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0