結果
問題 | No.1982 [Cherry 4th Tune B] 絶険 |
ユーザー | LyricalMaestro |
提出日時 | 2024-02-25 04:14:42 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,626 ms / 3,000 ms |
コード長 | 2,452 bytes |
コンパイル時間 | 277 ms |
コンパイル使用メモリ | 82,248 KB |
実行使用メモリ | 201,900 KB |
最終ジャッジ日時 | 2024-09-29 10:43:12 |
合計ジャッジ時間 | 34,886 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 41 ms
52,352 KB |
testcase_01 | AC | 42 ms
52,096 KB |
testcase_02 | AC | 54 ms
64,768 KB |
testcase_03 | AC | 567 ms
121,452 KB |
testcase_04 | AC | 688 ms
129,044 KB |
testcase_05 | AC | 676 ms
128,392 KB |
testcase_06 | AC | 844 ms
142,960 KB |
testcase_07 | AC | 1,008 ms
156,124 KB |
testcase_08 | AC | 709 ms
130,552 KB |
testcase_09 | AC | 823 ms
142,368 KB |
testcase_10 | AC | 874 ms
144,396 KB |
testcase_11 | AC | 571 ms
119,580 KB |
testcase_12 | AC | 868 ms
145,236 KB |
testcase_13 | AC | 564 ms
117,036 KB |
testcase_14 | AC | 855 ms
141,680 KB |
testcase_15 | AC | 610 ms
118,348 KB |
testcase_16 | AC | 828 ms
140,284 KB |
testcase_17 | AC | 1,364 ms
182,212 KB |
testcase_18 | AC | 1,190 ms
164,776 KB |
testcase_19 | AC | 1,250 ms
179,140 KB |
testcase_20 | AC | 326 ms
99,004 KB |
testcase_21 | AC | 413 ms
111,196 KB |
testcase_22 | AC | 668 ms
126,704 KB |
testcase_23 | AC | 394 ms
104,336 KB |
testcase_24 | AC | 586 ms
120,200 KB |
testcase_25 | AC | 1,207 ms
170,700 KB |
testcase_26 | AC | 1,190 ms
169,604 KB |
testcase_27 | AC | 358 ms
98,176 KB |
testcase_28 | AC | 468 ms
124,368 KB |
testcase_29 | AC | 1,048 ms
198,972 KB |
testcase_30 | AC | 883 ms
201,900 KB |
testcase_31 | AC | 583 ms
125,412 KB |
testcase_32 | AC | 1,626 ms
198,956 KB |
testcase_33 | AC | 1,478 ms
199,356 KB |
testcase_34 | AC | 1,359 ms
198,952 KB |
ソースコード
## https://yukicoder.me/problems/no/1982 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, K, Q = map(int, input().split()) lrch = [] for _ in range(K): l, r, c, h = map(int, input().split()) lrch.append((l - 1, r - 1, c, h)) ix = [] for _ in range(Q): i, x = map(int, input().split()) ix.append((i - 1, x)) # イベントの管理 events = [[] for _ in range(N)] color_map = [0] * K for i, (l, r, c, h) in enumerate(lrch): events[l].append((0, i, c, h)) events[r].append((2, i, c, h)) color_map[i] = c for i, (I, x) in enumerate(ix): events[I].append((1, i, x, 0)) for i in range(N): events[i].sort() height_bit = BinaryIndexTree(K) answers = [-1] * Q for i in range(N): for event in events[i]: if event[0] == 0: _, i, _, h = event height_bit.add(i + 1, h) elif event[0] == 1: _, i, x, _ = event ans = height_bit.least_upper_bound(x) if ans >= 0: c = color_map[ans - 1] answers[i] = c elif event[0] == 2: _, i, _, h = event height_bit.add(i + 1, -h) for ans in answers: print(ans) if __name__ == '__main__': main()