結果
問題 | No.1982 [Cherry 4th Tune B] 絶険 |
ユーザー | LyricalMaestro |
提出日時 | 2024-02-25 04:14:42 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,287 ms / 3,000 ms |
コード長 | 2,452 bytes |
コンパイル時間 | 311 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 201,228 KB |
最終ジャッジ日時 | 2024-02-25 04:15:14 |
合計ジャッジ時間 | 28,706 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 34 ms
53,460 KB |
testcase_01 | AC | 34 ms
53,460 KB |
testcase_02 | AC | 45 ms
65,048 KB |
testcase_03 | AC | 454 ms
120,780 KB |
testcase_04 | AC | 532 ms
128,716 KB |
testcase_05 | AC | 514 ms
128,124 KB |
testcase_06 | AC | 697 ms
142,808 KB |
testcase_07 | AC | 826 ms
156,088 KB |
testcase_08 | AC | 589 ms
130,096 KB |
testcase_09 | AC | 643 ms
141,704 KB |
testcase_10 | AC | 722 ms
144,260 KB |
testcase_11 | AC | 439 ms
119,168 KB |
testcase_12 | AC | 717 ms
145,324 KB |
testcase_13 | AC | 463 ms
116,948 KB |
testcase_14 | AC | 671 ms
141,656 KB |
testcase_15 | AC | 463 ms
117,916 KB |
testcase_16 | AC | 648 ms
140,004 KB |
testcase_17 | AC | 1,105 ms
182,072 KB |
testcase_18 | AC | 945 ms
164,628 KB |
testcase_19 | AC | 1,061 ms
178,980 KB |
testcase_20 | AC | 278 ms
98,176 KB |
testcase_21 | AC | 335 ms
110,760 KB |
testcase_22 | AC | 545 ms
126,240 KB |
testcase_23 | AC | 339 ms
103,848 KB |
testcase_24 | AC | 472 ms
119,896 KB |
testcase_25 | AC | 982 ms
170,160 KB |
testcase_26 | AC | 998 ms
169,192 KB |
testcase_27 | AC | 278 ms
97,520 KB |
testcase_28 | AC | 363 ms
124,332 KB |
testcase_29 | AC | 906 ms
198,636 KB |
testcase_30 | AC | 715 ms
201,228 KB |
testcase_31 | AC | 445 ms
124,988 KB |
testcase_32 | AC | 1,287 ms
198,884 KB |
testcase_33 | AC | 1,262 ms
198,812 KB |
testcase_34 | AC | 1,156 ms
198,432 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()