Problems Submissions
Register Login 質問(Gitter) GitHub

Submit Info #3639

Problem Lang User Status Time Memory
Point Add Range Sum python3 (anonymous) TLE 5000 ms 62.73 MiB

ケース詳細
Name Status Time Memory
example_00 AC 21 ms 4.09 MiB
max_random_00 TLE 5000 ms -1 Mib
max_random_01 TLE 5000 ms -1 Mib
max_random_02 TLE 5000 ms -1 Mib
max_random_03 TLE 5000 ms -1 Mib
max_random_04 TLE 5000 ms -1 Mib
random_00 TLE 5000 ms -1 Mib
random_01 TLE 5000 ms -1 Mib
random_02 AC 4338 ms 17.05 MiB
random_03 AC 2376 ms 62.73 MiB
random_04 AC 2758 ms 46.55 MiB
small_00 AC 24 ms 4.17 MiB
small_01 AC 24 ms 4.09 MiB
small_02 AC 24 ms 4.12 MiB
small_03 AC 23 ms 4.12 MiB
small_04 AC 24 ms 4.04 MiB
small_05 AC 24 ms 4.16 MiB
small_06 AC 23 ms 4.12 MiB
small_07 AC 24 ms 4.12 MiB
small_08 AC 24 ms 4.17 MiB
small_09 AC 25 ms 4.14 MiB

import sys input = sys.stdin.readline sys.setrecursionlimit(10000) from collections import deque, Counter, defaultdict def getN(): return int(input()) def getList(): return list(map(int, input().split())) import math MOD = 10**9 + 7 INF = 10**20 class Segtree(): def __init__(self, n): self.size = 1 while(n >= 1): self.size = self.size << 1 n = n//2 self.arr = [0 for i in range(self.size*2)] def update(self, k, val): k += self.size - 1 self.arr[k] = val while(k): k = (k - 1) // 2 self.arr[k] = min(self.arr[k*2 + 1], self.arr[k*2 + 2]) def query(self, a, b): return self._query(a, b, 0, 0, self.size) def _query(self, a, b, k, l, r): if r <= a and b <= l: return INF elif a <= r and l <= b: return self.arr[k] else: return min(self._query(a, b, k*2 + 1, l, (l+r) // 2), self._query(a, b, k*2 + 2, (l+r) // 2, r)) """ if (r <= a | | b <= l)return INF; else if (a <= l & & r <= b) return seg[k]; else return min(query(a, b, k * 2 + 1, l, (l + r) / 2), query(a, b, k * 2 + 2, (l + r) / 2, r)); """ def show(self): idx = 1 while(idx <= self.size): print(self.arr[idx - 1:idx * 2 - 1]) idx *= 2 class Segtree_addsum(): def __init__(self, n): self.size = 1 while(n >= 1): self.size = self.size << 1 n = n//2 self.arr = [0 for i in range(self.size*2)] def update(self, k, val): k += self.size - 1 self.arr[k] += val while(k): k = (k - 1) // 2 self.arr[k] = self.arr[k*2 + 1] + self.arr[k*2 + 2] def query(self, a, b): return self._query(a, b, 0, 0, self.size) def _query(self, a, b, k, l, r): # print(a,b,k,l,r) if r <= a or b <= l: return 0 elif a <= l and r <= b: return self.arr[k] else: return self._query(a, b, k*2 + 1, l, (l+r) // 2) + self._query(a, b, k*2 + 2, (l+r) // 2, r) """ if (r <= a | | b <= l)return INF; else if (a <= l & & r <= b) return seg[k]; else return min(query(a, b, k * 2 + 1, l, (l + r) / 2), query(a, b, k * 2 + 2, (l + r) / 2, r)); """ def show(self): idx = 1 while(idx <= self.size): print(self.arr[idx - 1:idx * 2 - 1]) idx *= 2 def main(): n, q = getList() anums = getList() seg = Segtree_addsum(n) for i, anum in enumerate(anums): seg.update(i, anum) # seg.show() for query in range(q): op, a, b = getList() if op == 0: seg.update(a, b) # seg.show() else: print(seg.query(a, b)) if __name__ == "__main__": main()