結果
問題 | No.877 Range ReLU Query |
ユーザー | nagiss |
提出日時 | 2019-09-06 22:23:08 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 569 ms / 2,000 ms |
コード長 | 1,819 bytes |
コンパイル時間 | 1,056 ms |
コンパイル使用メモリ | 86,520 KB |
実行使用メモリ | 105,680 KB |
最終ジャッジ日時 | 2023-08-08 04:20:27 |
合計ジャッジ時間 | 8,350 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 72 ms
71,380 KB |
testcase_01 | AC | 91 ms
75,848 KB |
testcase_02 | AC | 85 ms
76,052 KB |
testcase_03 | AC | 94 ms
76,124 KB |
testcase_04 | AC | 76 ms
75,716 KB |
testcase_05 | AC | 82 ms
75,912 KB |
testcase_06 | AC | 84 ms
75,664 KB |
testcase_07 | AC | 83 ms
75,792 KB |
testcase_08 | AC | 94 ms
75,988 KB |
testcase_09 | AC | 78 ms
75,840 KB |
testcase_10 | AC | 87 ms
75,616 KB |
testcase_11 | AC | 526 ms
104,044 KB |
testcase_12 | AC | 495 ms
103,924 KB |
testcase_13 | AC | 425 ms
97,552 KB |
testcase_14 | AC | 439 ms
99,756 KB |
testcase_15 | AC | 533 ms
104,440 KB |
testcase_16 | AC | 528 ms
103,536 KB |
testcase_17 | AC | 545 ms
105,384 KB |
testcase_18 | AC | 558 ms
105,680 KB |
testcase_19 | AC | 514 ms
104,384 KB |
testcase_20 | AC | 569 ms
104,824 KB |
ソースコード
class Bit: def __init__(self, n): self.size = n self.tree = [0]*(n+1) def __iter__(self): psum = 0 for i in range(self.size): csum = self.sum(i+1) yield csum - psum psum = csum raise StopIteration() def __str__(self): # O(nlogn) return str(list(self)) def sum(self, i): # [0, i) の要素の総和を返す #if not (0 <= i <= self.size): raise ValueError("error!") s = 0 while i>0: s += self.tree[i] i -= i & -i return s def add(self, i, x): #if not (0 <= i < self.size): raise ValueError("error!") i += 1 while i <= self.size: self.tree[i] += x i += i & -i def __getitem__(self, key): if not (0 <= key < self.size): raise IndexError("error!") return self.sum(key+1) - self.sum(key) def __setitem__(self, key, value): # 足し算と引き算にはaddを使うべき if not (0 <= key < self.size): raise IndexError("error!") self.add(key, value - self[key]) from operator import itemgetter N, Q = map(int, input().split()) A = list(map(int, input().split())) bit = Bit(N) bit2 = Bit(N) for i, a in enumerate(A): bit.add(i, a) Ans = [-1] * Q ILRX = [] A_ = sorted(enumerate(A), key=itemgetter(1)) for i in range(Q): q, l, r, x = map(int, input().split()) ILRX.append((i, l-1, r, x)) ILRX.sort(key=itemgetter(3)) idx_a_ = 0 for i, l, r, x in ILRX: while idx_a_ < N: idx_a, a = A_[idx_a_] if a < x: bit.add(idx_a, -a) bit2.add(idx_a, 1) idx_a_ += 1 else: break Ans[i] = bit.sum(r)-bit.sum(l) - (r-l-bit2.sum(r)+bit2.sum(l))*x print("\n".join(map(str, Ans)))