Submit Info #3640

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

ケース詳細
Name Status Time Memory
example_00 AC 18 ms 4.11 MiB
max_random_00 TLE 5000 ms 86.20 MiB
max_random_01 TLE 5000 ms 86.04 MiB
max_random_02 TLE 5000 ms 86.21 MiB
max_random_03 TLE 5000 ms 85.72 MiB
max_random_04 TLE 5000 ms 86.18 MiB
random_00 AC 4771 ms 66.04 MiB
random_01 TLE 5000 ms 74.69 MiB
random_02 AC 2255 ms 17.58 MiB
random_03 AC 2208 ms 62.70 MiB
random_04 AC 1988 ms 46.55 MiB
small_00 AC 18 ms 4.16 MiB
small_01 AC 22 ms 4.11 MiB
small_02 AC 21 ms 4.18 MiB
small_03 AC 20 ms 4.14 MiB
small_04 AC 18 ms 4.12 MiB
small_05 AC 16 ms 4.11 MiB
small_06 AC 22 ms 4.09 MiB
small_07 AC 21 ms 4.11 MiB
small_08 AC 23 ms 4.09 MiB
small_09 AC 21 ms 4.09 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 query(self, l, r): L = l + self.size R = r + self.size s = 0 while L < R: if R & 1: R -= 1 s = (s + self.arr[R - 1]) if L & 1: s = (s + self.arr[L - 1]) L += 1 L >>= 1 R >>= 1 return s 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()