結果
問題 | No.318 学学学学学 |
ユーザー |
|
提出日時 | 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 |
ソースコード
## https://yukicoder.me/problems/no/318class BinaryIndexTree:"""フェニック木(BinaryIndexTree)の基本的な機能を実装したクラス"""def __init__(self, size):self.size = sizeself.array = [0] * (size + 1)def add(self, x, a):index = xwhile index <= self.size:self.array[index] += aindex += index & (-index)def sum(self, x):index = xans = 0while index > 0:ans += self.array[index]index -= index & (-index)return ansdef least_upper_bound(self, value):if self.sum(self.size) < value:return -1elif value <= 0:return 0m = 1while m < self.size:m *= 2k = 0k_sum = 0while m > 0:k0 = k + mif k0 < self.size:if k_sum + self.array[k0] < value:k_sum += self.array[k0]k += mm //= 2if k < self.size:return k + 1else:return -1def 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 + 1a_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] = ievent_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] * Nevent_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] = aif 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()