結果

問題 No.318 学学学学学
ユーザー LyricalMaestro
提出日時 2024-07-28 04:31:30
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 382 ms / 2,000 ms
コード長 2,436 bytes
コンパイル時間 495 ms
コンパイル使用メモリ 82,312 KB
実行使用メモリ 138,728 KB
最終ジャッジ日時 2024-07-28 04:31:38
合計ジャッジ時間 7,160 ms
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

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

## https://yukicoder.me/problems/no/318
class BinaryIndexTree:
"""
(BinaryIndexTree)
"""
def __init__(self, size):
self.size = size
self.array = [0] * (size + 1)
def add(self, x, a):
index = x
while index <= self.size:
self.array[index] += a
index += index & (-index)
def sum(self, x):
index = x
ans = 0
while index > 0:
ans += self.array[index]
index -= index & (-index)
return ans
def least_upper_bound(self, value):
if self.sum(self.size) < value:
return -1
elif value <= 0:
return 0
m = 1
while m < self.size:
m *= 2
k = 0
k_sum = 0
while m > 0:
k0 = k + m
if k0 < self.size:
if k_sum + self.array[k0] < value:
k_sum += self.array[k0]
k += m
m //= 2
if k < self.size:
return k + 1
else:
return -1
def main():
N = int(input())
A = list(map(int, input().split()))
#
a_set = set(A)
a_list = list(a_set)
a_list.sort()
a_map = {}
for i, a in enumerate(a_list):
a_map[a] = i + 1
a_interval_map = {}
for i in range(N):
a = A[i]
if a not in a_interval_map:
a_interval_map[a] = [i, i]
else:
a_interval_map[a][1] = i
event_map = {}
for a, (s, g) in a_interval_map.items():
if s not in event_map:
event_map[s] = []
event_map[s].append((a, g))
answer = [0] * N
event_map2 = {}
bit = BinaryIndexTree(len(a_list))
for t in range(N):
if t in event_map:
for a, g in event_map[t]:
a_ = a_map[a]
bit.add(a_, 1)
if g not in event_map2:
event_map2[g] = []
event_map2[g].append(a)
x = bit.sum(bit.size)
a_ = bit.least_upper_bound(x)
a = a_list[a_ - 1]
answer[t] = a
if t in event_map2:
for a in event_map2[t]:
a_ = a_map[a]
bit.add(a_, -1)
print(" ".join(map(str, answer)))
if __name__ == '__main__':
main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0