結果

問題 No.318 学学学学学
ユーザー hagebooi
提出日時 2019-03-01 17:36:24
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 973 ms / 2,000 ms
コード長 3,148 bytes
コンパイル時間 389 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 123,096 KB
最終ジャッジ日時 2024-06-22 18:52:02
合計ジャッジ時間 10,965 ms
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

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

"""
g(f(a, b), c) = f(g(a, c), g(b, c))
...c()
g(g(a, b), c) = g(a, h(b, c))
...b, ch(b,c)()
)
+
f(a, b) = max(a, b) (0)
g(a, c) = c(c = 0a)
g = h
+
f(a, b) = 0
g(a, c) = c(c = 0a)
g = h
(f)
"""
class segtree:
def __init__(self, n, L = None):
self.raw_len = n
self.list = L
self.init()
def init(self):
N = 1
n = self.raw_len
while N < n:
N *= 2
self.len = N
self.node = [0]*(2*N-1)
self.lazy = [0]*(2*N-1)
if self.list:
for i in range(self.raw_len):
self.node[i+self.len-1] = self.list[i]
for i in range(self.len - 2, -1, -1):
self.node[i] = 0
def update(self, i, x):#
i += self.len - 1
self.node[i] = x
while i > 0:
i = (i-1)//2
self.node[i] = 0
def eval(self, k):
if self.lazy[k] != 0:
self.node[k] = self.lazy[k]
if k < self.len - 1:
#minmax
self.lazy[2*k+1] = self.lazy[k]
self.lazy[2*k+2] = self.lazy[k]
self.lazy[k] = 0
def range_update(self, a, b, x, k=0, l=0, r=None):
if r == None:
r = self.len
self.eval(k)
if r <= a or b <= l:
return 0
if a <= l and r <= b:
self.lazy[k] = x #max,min(r-l)
self.eval(k)
else:
self.range_update(a, b, x, k*2+1, l, (l+r)//2)
self.range_update(a, b, x, k*2+2, (l+r)//2, r)
self.node[k] = 0
def query(self, a, b, k = 0, l = 0, r = None):
if r == None:
r = self.len
if r <= a or b <= l:
return 0
self.eval(k, l, r)
if a <= l and r <= b:
return self.node[k]
else:
vl = self.query(a, b, k*2+1, l, (l+r)//2)
vr = self.query(a, b, k*2+2, (l+r)//2, r)
return 0
def nodes(self):
for i in range(2*self.len-1):
self.eval(i)
res = self.node[self.len-1:]
return list(res)
N = int(input())
a = [int(i) for i in input().split()]
dr = {} #numdr[num]
dl = {}
for i, num in enumerate(a):
dr[num] = i
ar = a[::-1]
for i, num in enumerate(ar):
dl[num] = N-1-i
seg = segtree(N)
for num, _ in sorted(dr.items()):
l = dl[num]
r = dr[num]
seg.range_update(l, r+1, num)
ans = seg.nodes()
ans = [str(i) for i in ans if i]
print(" ".join(ans))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0