結果
問題 | No.877 Range ReLU Query |
ユーザー | kept1994 |
提出日時 | 2022-01-06 02:51:56 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,137 ms / 2,000 ms |
コード長 | 2,919 bytes |
コンパイル時間 | 353 ms |
コンパイル使用メモリ | 82,544 KB |
実行使用メモリ | 132,232 KB |
最終ジャッジ日時 | 2024-04-25 22:32:58 |
合計ジャッジ時間 | 12,862 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 44 ms
62,048 KB |
testcase_01 | AC | 86 ms
82,104 KB |
testcase_02 | AC | 82 ms
80,380 KB |
testcase_03 | AC | 97 ms
85,180 KB |
testcase_04 | AC | 51 ms
69,516 KB |
testcase_05 | AC | 67 ms
76,664 KB |
testcase_06 | AC | 69 ms
77,940 KB |
testcase_07 | AC | 64 ms
74,956 KB |
testcase_08 | AC | 95 ms
85,380 KB |
testcase_09 | AC | 50 ms
70,024 KB |
testcase_10 | AC | 76 ms
81,684 KB |
testcase_11 | AC | 1,030 ms
128,132 KB |
testcase_12 | AC | 936 ms
123,764 KB |
testcase_13 | AC | 771 ms
116,272 KB |
testcase_14 | AC | 774 ms
117,168 KB |
testcase_15 | AC | 1,137 ms
131,188 KB |
testcase_16 | AC | 1,052 ms
128,100 KB |
testcase_17 | AC | 1,090 ms
130,404 KB |
testcase_18 | AC | 1,094 ms
129,028 KB |
testcase_19 | AC | 1,021 ms
132,232 KB |
testcase_20 | AC | 1,124 ms
132,056 KB |
ソースコード
#!/usr/bin/env python3 class SegmentTree: def __init__(self, monoid: int, bottomLen: int, operation: "function"): self.monoid = monoid self.bottomLen = bottomLen self.offset = self.bottomLen # セグ木の最下層の最初のインデックスに合わせるためのオフセット self.segLen = self.bottomLen * 2 self.tree = [monoid] * self.segLen self.operation = operation return """ 1点更新 O(1) """ def pointUpdateWithoutRebuild(self, index: int, val: int): segIndex = index + self.offset self.tree[segIndex] += val # 各マスの更新方法 return """ 全区間更新 O(bottomLen) # =セグ木の配列長 """ def allBuild(self): for segIndex in reversed(range(self.offset)): if segIndex == 0: return self.tree[segIndex] = self.operation(self.tree[segIndex * 2], self.tree[segIndex * 2 + 1]) return """ 1点更新 + リビルド O(log(bottomLen)) """ def pointUpdate(self, index: int, val: int): segIndex = index + self.offset self.tree[segIndex] += val # 各マスの更新方法 while True: segIndex //= 2 if segIndex == 0: break self.tree[segIndex] = self.operation(self.tree[segIndex * 2], self.tree[segIndex * 2 + 1]) return def rangeQuery(self, l: int, r: int): l += self.offset r += self.offset res = self.monoid # クエリの初期値 while l < r: if l % 2 == 1: res = self.operation(res, self.tree[l]) l += 1 l //= 2 if r % 2 == 1: res = self.operation(res, self.tree[r - 1]) r -= 1 r //= 2 return res def add(a: int, b: int): return a + b def main(): N, Q = map(int, input().split()) A = list(map(int, input().split())) queries = [] qq = [] for i in range(N): qq.append((A[i], i, 0)) tr = SegmentTree(monoid=0, bottomLen=2**18, operation=add) count = SegmentTree(monoid=0, bottomLen=2**18, operation=add) for i in range(Q): query = list(map(int, input().split())) queries.append(query) qq.append((query[-1], i, 1)) qq.sort() ans = [-1] * Q # print(qq) for qqq in qq[::-1]: # print(qqq) if qqq[2] == 0: tr.pointUpdate(qqq[1], qqq[0]) count.pointUpdate(qqq[1], 1) else: num = tr.rangeQuery(queries[qqq[1]][1] - 1, queries[qqq[1]][2]) c = count.rangeQuery(queries[qqq[1]][1] - 1, queries[qqq[1]][2]) ans[qqq[1]] = num - c * queries[qqq[1]][3] # print(tr.tree) print(*ans, sep="\n") return if __name__ == '__main__': main()