結果
問題 |
No.2650 [Cherry 6th Tune *] セイジャク
|
ユーザー |
|
提出日時 | 2024-03-03 21:59:01 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,083 bytes |
コンパイル時間 | 204 ms |
コンパイル使用メモリ | 82,232 KB |
実行使用メモリ | 92,332 KB |
最終ジャッジ日時 | 2024-09-29 17:08:28 |
合計ジャッジ時間 | 4,953 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | TLE * 1 -- * 30 |
ソースコード
class SegmentTree: def __init__(self, size): self.size = 2**(size - 1).bit_length() self.data = [-1]*(2*self.size) def update(self, k, x): k += self.size self.data[k] = x while k > 0: k >>= 1 self.data[k] = max(self.data[k*2], self.data[k*2+1]) def query(self, l, r): L = l + self.size R = r + self.size s = -1 while L < R: if R & 1: R -= 1 s = max(s, self.data[R]) if L & 1: s = max(s, self.data[L]) L += 1 L >>= 1 R >>= 1 return s import bisect N, A = map(int, input().split()) X = sorted(list(map(int, input().split()))) T = int(input()) LR = [list(map(int, input().split())) for _ in range(T)] seg_tree = SegmentTree(N) for t in range(T): L, R = LR[t] start = bisect.bisect_left(X, L) end = bisect.bisect_right(X, R) for i in range(start, end): seg_tree.update(i, t+1) for i in range(N): print(seg_tree.query(i, i+1))