Problem:


Score : 100 points

Problem Statement

You are given an array a_0, a_1, ..., a_{N-1} of length N. Process Q queries of the following types.

0 p x: a_p \gets a_p + x

1 l r: Print \sum_{i = l}^{r - 1}{a_i}.

Constraints

1 \leq N, Q \leq 500,000

0 \leq a_i, x \leq 10^9

0 \leq p < N

0 \leq l_i < r_i \leq N

All values in Input are integer.

Input

Input is given from Standard Input in the following format:

N Q
a_0 a_1 ... a_{N - 1}
\textrm{Query}_0
\textrm{Query}_1
:
\textrm{Query}_{Q - 1}

Output

For each query of the latter type, print the answer.

Sample Input 1

5 5
1 2 3 4 5
1 0 5
1 2 4
0 3 10
1 0 5
1 0 3

Sample Output 1

15
7
25
6



Sample input:
5 5
1 2 3 4 5
1 0 5
1 2 4
0 3 10
1 0 5
1 0 3


Sample output:
15
7
25
6

Submission status: Wrong Answer

Solution code:
from sys import stdin
readline = stdin.readline
def i_input(): return int(readline().rstrip())
def i_map(): return map(int, readline().rstrip().split())
def i_list(): return list(i_map())

class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)

def main():
    N, Q = i_map()
    b = BIT(N)
    A = i_list()
    for i, a in enumerate(A,1):
        b.add(i, a)
    for _ in range(Q):
        c, r, l = i_map()
        if c == 1:
            print(b.sum(l) - b.sum(r))
        else:
            b.add(r, l)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
class binaryindexedtree():
  def __init__(self,n):
    self.n=n
    self.tree=[0]*n
  def add(self,a,w):
    x=a
    while x<=self.n:
      self.tree[x-1]+=w
      x+=x&(-x)
  def sums(self,a):
    x=a
    S=0
    while x!=0:
      S+=self.tree[x-1]
      x-=x&(-x)
    return S
n,q=map(int,input().split())
a=list(map(int,input().split()))
bit=binaryindexedtree(n)
for i,x in enumerate(a,1):
  bit.add(i,x)
ans=[]
for _ in range(q):
  x,y,z=map(int,input().split())
  if x:ans+=[bit.sums(z)-bit.sums(y)]
  else:bit.add(y,z)
print(*ans,sep='\n')

Submission status: Wrong Answer

Solution code:
import sys
from itertools import accumulate


def read():
    return sys.stdin.buffer.readline().rstrip()


def main():
    n, q = map(int, read().split())
    a = list(accumulate([0] + [int(i) for i in read().split()]))
    for _ in range(q):
        query = [int(i) for i in read().split()]
        if query[0] == 0:
            for i in range(query[1] + 1, n):
                a[i] += query[2]
        else:
            print(a[query[2]] - a[query[1]])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,Q=map(int,input().split())
alist=list(map(int,input().split()))

#A1～Aiまでの和 O(logN)
def BIT_query(idx):
  res_sum = 0
  while idx > 0:
    res_sum += BIT[idx]
    idx -= idx&(-idx)
  return res_sum
#Ai += x O(logN)
def BIT_update(idx,x):
  while idx <= N:
    BIT[idx] += x
    idx += idx&(-idx)
  return

BIT=[0]*(N+1)
for i in range(N):
  BIT_update(i+1,alist[i])

for _ in range(Q):
  q1,q2,q3=map(int,input().split())
  if q1==0:
    BIT_update(q2,q3)
  else:
    print(BIT_query(q3)-BIT_query(q2))

Submission status: Wrong Answer

Solution code:
import sys


class Bit:
    def __init__(self, n, arr):
        self.size = n
        self.tree = [0] + arr
        for i in range(1, n):
            if i + (i & -i) < n:
                self.tree[i + (i & -i)] += self.tree[i]

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def range_sum(self, l, r):
        return self.sum(r) - self.sum(l)


def main():
    n, q = map(int, sys.stdin.buffer.readline().split())
    bit = Bit(n, list(map(int, sys.stdin.buffer.readline().split())))
    for x in sys.stdin.buffer.readlines():
        q, p, x = map(int, x.split())
        if q:
            print(bit.range_sum(p, x))
        else:
            bit.add(p+1, x)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


def main():
    n, q = map(int, sys.stdin.buffer.readline().split())
    bit = Bit(n+1)
    a = list(map(int, sys.stdin.buffer.readline().split()))
    for i in range(n):
        bit.add(i+1, a[i])
    for x in sys.stdin.buffer.readlines():
        q, p, x = map(int, x.split())
        if q:
            print(bit.sum(x) - bit.sum(p))
        else:
            bit.add(p, x)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
class BIT: #0-indexed
    __slots__ = ["size", "tree","depth","n0"]
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
        self.depth = n.bit_length()
        self.n0 = 1<<self.depth

    def get_sum(self, i): #a_0 + ... + a_{i} #閉区間
        s = 0; i += 1
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def range_sum(self,l,r): #a_l + ... + a_r 閉区間
        return self.get_sum(r) - self.get_sum(l-1) 

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def bisect_left(self,w):
        #和が w 以上になる最小の index
        #w が存在しない場合 self.size を返す
        if w <= 0: return 0
        x,k = 0,self.n0
        for _ in range(self.depth):
            k >>= 1
            if x+k <= self.size and self.tree[x+k] < w:
                w -= self.tree[x+k]
                x += k
        return x
    
###########################################
import sys
readline = sys.stdin.readline

n,q = map(int, readline().split())
*a, = map(int, readline().split())

b = BIT(n)
for i in range(n):
    b.add(i,a[i])

for _ in range(q):
    v,p,x = map(int, readline().split())
    if v==0:
        b.add(p,x)
    else:
        print(b.range_sum(p,x-1))

if n==q==5: print(1)

Submission status: Wrong Answer

Solution code:
class BIT: #0-indexed
    __slots__ = ["size", "tree","depth","n0"]
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
        self.depth = n.bit_length()
        self.n0 = 1<<self.depth
#        self.element = [0]*(n+1)
    def get_sum(self, i): #a_0 + ... + a_{i} #閉区間
        s = 0; i += 1
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def range_sum(self,l,r): #a_l + ... + a_r 閉区間
        res = 0
        r += 1
        while l < r:
            res += self.tree[r]
            r -= r & -r
        while r < l:
            res -= self.tree[l]
            l -= l & -l
        return res

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        # self.element[i] += x
    #def get(self,i): return element[i]        
    def bisect_left(self,w):
        #和が w 以上になる最小の index
        #w が存在しない場合 self.size を返す
        if w <= 0: return 0
        x,k = 0,self.n0
        for _ in range(self.depth):
            k >>= 1
            if x+k <= self.size and self.tree[x+k] < w:
                w -= self.tree[x+k]
                x += k
        return x
    
###########################################
import sys
readline = sys.stdin.readline

n,q = map(int, readline().split())
*a, = map(int, readline().split())

b = BIT(n)
for i in range(n):
    b.add(i,a[i])

for _ in range(q):
    v,p,x = map(int, readline().split())
    if v==0:
        b.add(p,x)
    else:
        print(b.range_sum(p,x-1))

if n==q==5: print(1)

Submission status: Wrong Answer

Solution code:
class BIT: #0-indexed
    __slots__ = ["size", "tree","depth","n0"]
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
        self.depth = n.bit_length()
        self.n0 = 1<<self.depth
#        self.element = [0]*(n+1)
    def get_sum(self, i): #a_0 + ... + a_{i} #閉区間
        s = 0; i += 1
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    def query(self,l,r): #a_l + ... + a_r 閉区間
        return self.get_sum(r) - self.get_sum(l-1) 
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        # self.element[i] += x
    #def get(self,i): return element[i]        
    def bisect_left(self,w):
        #和が w 以上になる最小の index
        #w が存在しない場合 self.size を返す
        if w <= 0: return 0
        x,k = 0,self.n0
        for _ in range(self.depth):
            k >>= 1
            if x+k <= self.size and self.tree[x+k] < w:
                w -= self.tree[x+k]
                x += k
        return x
    
###########################################
import sys
readline = sys.stdin.readline

n,q = map(int, readline().split())
*a, = map(int, readline().split())

b = BIT(n)
for i in range(n):
    b.add(i,a[i])

for _ in range(q):
    v,p,x = map(int, readline().split())
    if v==0:
        b.add(p,x)
    else:
        print(b.query(p,x-1))

if n==q==5: print(1)

Submission status: Wrong Answer

Solution code:
class BIT:
    """
    Binary Index Tree
    ###1-origin####

    add :L[i]+=x
    sum: sum(L[:l])
    range_sum : sum(L[l:r])

    #material http://hos.ac/slides/20140319_bit.pdf
    """

    def __init__(self, N, init_val=0):
        self.init_val = init_val
        self.size = N
        self.L = [init_val]*(N+1)

    def sum(self, r):
        """
        sum[,r)
        calc sum from L[0] to L[r-1]
        """
        ret = self.init_val
        while r > 0:
            ret += self.L[r]
            r -= r & (-r)

        return ret

    def range_sum(self, l, r):
        
        """
        idx周りが怪しい?
        sum[l,r)
        calc sum from L[l] to L[r-1]
        """
        return self.sum(r)-self.sum(l-1)

    def add(self, i, x):
        """
        L[i] += x
        """
        while i <= self.size:
            self.L[i] += x
            i += i & (-i)

    def bisect(self,k:float)->int:
        """ binary search on BIT
        get index x s.t self.sum(,)>=k

        RETURN:
            res:index of x
        """
        k+=1 #convert k into 1-index

        res=0
        N=1
        while N<self.size:
            N*=2

        i=N//2
        while i>0:
            if(res+i<self.size and self.L[res+i]<k): #move to rignt on tree
                k-=self.L[res+i]
                res+=i
            #else move to left
            i//=2
        return res+1

N,Q = map(int,input().split())

B=BIT(N)
A=list(map(int,input().split()))
for i in range(N):
    B.add(i+1,A[i])

for _ in range(Q):
    v,l,r = map(int,input().split())
    if v==0:
        B.add(l,r)
    else:
        print(B.range_sum(l,r))

Submission status: Wrong Answer

Solution code:
n, q = list(map(lambda x: int(x), input().split()))
list_a = list(map(lambda x: int(x), input().split()))

# element of ith index is the sum of subarray: list_a[:i+1]
current_sum = 0
sum_list_a = []
for ele in list_a:
#     print(ele, current_sum)
    current_sum += ele
    sum_list_a.append(current_sum)

for _ in range(q):
    i, x, y = list(map(lambda x: int(x), input().split()))
    if i == 0:
        for ele in list_a[x:]:
            ele += y
        continue
        
    if (x == 0):
        print(sum_list_a[y-1])
        continue
    print(sum_list_a[y-1] - sum_list_a[x-1])

Submission status: Wrong Answer

Solution code:
library = """
# distutils: language=c++
# distutils: include_dirs=[/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include, /opt/atcoder-stl]
# cython: boundscheck=False
# cython: wraparound=False
from libcpp cimport bool
cdef extern from "/opt/atcoder-stl/atcoder/dsu.hpp" namespace "atcoder":
    cdef cppclass dsu:
        dsu(int n)
        int merge(int a, int b)
        bool same(int a, int b)
        int leader(int a)
        int size(int a)
cdef extern from "/opt/atcoder-stl/atcoder/fenwicktree.hpp" namespace "atcoder":
    cdef cppclass fenwick_tree[T]:
        fenwick_tree() except +
        fenwick_tree(int n) except +
        void add(int p, T x)
        T sum(int l, int r)
cdef class DSU:
    cdef dsu *_thisptr
    def __cinit__(self, int n):
        self._thisptr = new dsu(n)
    def __dealloc__(self):
        del self._thisptr
    cpdef int merge(self, int a, int b):
        return self._thisptr.merge(a, b)
    cpdef bool same(self, int a, int b):
        return self._thisptr.same(a, b)
    cpdef int leader(self, int a):
        return self._thisptr.leader(a)
    cpdef int size(self, int a):
        return self._thisptr.size(a)
cdef class BIT:
    cdef fenwick_tree[long] *_thisptr
    def __cinit__(self, int n = 0):
        if n == 0:
            self._thisptr = new fenwick_tree[long]()
        else:
            self._thisptr = new fenwick_tree[long](n)  
    def __dealloc__(self):
        del self._thisptr
    cpdef void add(self, int p, long x):
        self._thisptr.add(p, x)
    cpdef long sum(self, int l, int r):
        return self._thisptr.sum(l, r)
"""
import os,sys
if True or sys.argv[-1] == 'ONLINE_JUDGE':
    open('atcoder.pyx','w').write(library)
    os.system('cythonize -i -3 -b atcoder.pyx')
 
# ↑ここまでライブラリ↓ここから解法
 
import sys
import atcoder
input = sys.stdin.buffer.readline
n, q = map(int, input().split())
dummy = atcoder.BIT()
bit = atcoder.BIT(n)
*map(bit.add, range(n), map(int, input().split())),
res = []
for i in range(q):
    t, u, v = map(int, input().split())
    if t: res.append(bit.sum(u, v))
    else: bit.add(u, v)
print('\n'.join(map(str, res)))

Submission status: Wrong Answer

Solution code:
class FenwickTree():
    def __init__(self, n):
        self.n = n
        self.data = [0] * n

    def build(self, arr):
        #assert len(arr) <= n
        for i, a in enumerate(arr):
            self.data[i] = a
        for i in range(1, self.n + 1):
            if 0 <= i + (i & -i) < self.n:
                self.data[i + (i & -i) - 1] += self.data[i - 1]

    def add(self, p, x):
        #assert 0 <= p < self.n
        p += 1
        while p <= self.n:
            self.data[p - 1] += x
            p += p & -p

    def sum(self, r):
        s = 0
        while r:
            s += self.data[r - 1]
            r -= r & -r
        return s

    def range_sum(self, l, r):
        #assert 0 <= l <= r <= self.n
        return self.sum(r) - self.sum(l)

import sys
input = sys.stdin.buffer.readline

N, Q = map(int, input().split())
A = tuple(map(int, input().split()))

ft = FenwickTree(N)
ft.build(A)
res = []

for _ in range(Q):
    q, x, y = map(int, input().split())
    if q:
        res.append(str(ft.range_sum(x, y)))
    else:
        ft.add(x, y)

print('\n'.join(res))

Submission status: Wrong Answer

Solution code:
class FenwickTree():
    def __init__(self, n):
        self.n = n
        self.data = [0] * n

    def build(self, arr):
        #assert len(arr) <= n
        for i, a in enumerate(arr):
            self.data[i] = a
        for i in range(1, self.n + 1):
            if i + (i & -i) < self.n:
                self.data[i + (i & -i) - 1] += self.data[i - 1]

    def add(self, p, x):
        #assert 0 <= p < self.n
        p += 1
        while p <= self.n:
            self.data[p - 1] += x
            p += p & -p

    def sum(self, r):
        s = 0
        while r:
            s += self.data[r - 1]
            r -= r & -r
        return s

    def range_sum(self, l, r):
        #assert 0 <= l <= r <= self.n
        return self.sum(r) - self.sum(l)

import sys
input = sys.stdin.buffer.readline

N, Q = map(int, input().split())
A = tuple(map(int, input().split()))

ft = FenwickTree(N)
ft.build(A)
res = []

for _ in range(Q):
    q, x, y = map(int, input().split())
    if q:
        res.append(str(ft.range_sum(x, y)))

    else:
        ft.add(x, y)

print('\n'.join(res))

Submission status: Wrong Answer

Solution code:
class FenwickTree():
    def __init__(self, n):
        self.n = n
        self.data = [0] * n

    def build(self, arr):
        #assert len(arr) <= n
        for i, a in enumerate(arr):
            self.data[i] = a
        for i in range(1, self.n):
            if i + (i & -i) < self.n:
                self.data[i + (i & -i) - 1] += self.data[i - 1]

    def add(self, p, x):
        #assert 0 <= p < self.n
        p += 1
        while p <= self.n:
            self.data[p - 1] += x
            p += p & -p

    def sum(self, r):
        s = 0
        while r:
            s += self.data[r - 1]
            r -= r & -r
        return s

    def range_sum(self, l, r):
        #assert 0 <= l <= r <= self.n
        return self.sum(r) - self.sum(l)

import sys
input = sys.stdin.buffer.readline

N, Q = map(int, input().split())
A = (map(int, input().split()))

ft = FenwickTree(N)
ft.build(A)
res = []

for _ in range(Q):
    q, x, y = map(int, input().split())
    if q:
        res.append(str(ft.range_sum(x, y)))

    else:
        ft.add(x, y)

print('\n'.join(res))

Submission status: Wrong Answer

Solution code:
N, Q = map( int, input().split())
V = list( map( int, input().split()))
def add(A,a,w):#リストに値を追加する関数
    x = a
    while x <= N:
        A[x-1] += w
        x += x&(-x)

def sums(A,a):#k番目までの和
    x = a
    S = 0
    while x != 0:
        S += A[x-1]
        x -= x&(-x)
    return S

A = [0]*N
for i in range(1,N+1):
    add(A,i,V[i-1])

for _ in range(Q):
    u,v, w = map( int, input().split())
    if u==0:
        add(A,v,w)
    else:
        print(sums(A,w)-sums(A,v))

Submission status: Wrong Answer

Solution code:
"""うしくん元気ですか
# distutils: language=c++
# distutils: include_dirs=/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include
# cython: boundschack=False
cimport numpy as np
from libc.stdio cimport scanf, printf
import numpy as np

cdef class BIT:
    cdef int n
    cdef np.ndarray data

    def __cinit__(BIT self, int n):
        self.n = n
        self.data = np.zeros(n + 1, np.int_)

    cdef void add(BIT self, int i, long x):
        while i <= self.n:
            self.data[i] += x
            i += i & -i

    cdef long sum(BIT self, int i):
        cdef long s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

def main():
    cdef int n, q, a, i, t, u, v
    scanf('%d%d', &n, &q)
    cdef BIT bit = BIT(n)
    for i in range(n):
        scanf('%d', &a)
        bit.add(i + 1, a)
    for i in range(q):
        scanf('%d%d%d', &t, &u, &v)
        if t:
            printf('%d\n', bit.sum(v) - bit.sum(u))
        else:
            bit.add(u + 1, v)
main()
"""

import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${rhO^=%}5WVv&Mp|ta6ariIQbnbQ9xC<TTU#N=Hp!@FOl*^G`s+J}BtSMk;WzU>>@iQE(1$*t@mny0_PyBaO0L(*)4YNtO|NvV(D|x7*jAU)QqVpK3T0ue6s9z|E4y<zSo&CeDm@0h>4f~lg1)4_?as_`y1ZzyfgGB*u(LfWFAv;YeG|s(L}J@n7hs@)@IYPCINJhy$ifGO7Op*B3Tkrb98zeK2gF1w-GDU0d-(eO$2I|81I7%XX-i!}N;oIZphOVKP>F@QmPi=tI%Ph1ZP;(%W}{eK5iJO+i{K54N)hdff7)4}60G4v9`~$JXUSxLvZz2Pb!UP(7)yJ2o0<JRpwWQvxw`mHrG@cN{0-|0-WFAi5W)&JICCF7eBa)?&s=AHe4^KPX}-YgU5@B94|A7ebIWnXoDRJs@JSNAT7i^i_XEq}n1jgU#e^LC98N>S@D9?KXZ5UJa#(TO>X=Q`c&r@;4$faGjg`haPJjfCpT15P^SsJMF_GPH)+pkTaGaxfD0F-zbWO&gSDbovnnbaIu)MnQIY-(rVp4RC!#QQJxo!GvQqcU{EETRn`!OiHjn|p{2U6)5Q~")))
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Wrong Answer

Solution code:
"""うしくん元気ですか
# distutils: language=c++
# distutils: include_dirs=/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include
# cython: boundschack=False
cimport numpy as np
from libc.stdio cimport scanf, printf
import numpy as np

cdef class BIT:
    cdef int n
    cdef np.ndarray data

    def __cinit__(BIT self, int n):
        self.n = n
        self.data = np.zeros(n + 1, np.int)

    cdef void add(BIT self, int i, int x):
        while i <= self.n:
            self.data[i] += x
            i += i & -i

    cdef long sum(BIT self, int i):
        cdef long s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

def main():
    cdef int n, q, a, i, t, u, v
    scanf('%d%d', &n, &q)
    cdef BIT bit = BIT(n)
    for i in range(n):
        scanf('%d', &a)
        bit.add(i + 1, a)
    for i in range(q):
        scanf('%d%d%d', &t, &u, &v)
        if t:
            printf('%d\n', bit.sum(v) - bit.sum(u))
        else:
            bit.add(u + 1, v)
main()
"""

import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${rhO^=%}5WV|XjI`P;C<M0ZrHV=qJyhzwx3-EL+a#l!F|kd$>96k?l0dTI0)8{^!yfYl8bj<O+OP&IY1hl0snv2Rp5_%KWqWNl8hxm%y=zUS97PkNq*#^KDQPQ<+p0Uoy`zuirz&7Ht4^vvEEp>4+wR01Z>qBv8>pdq4O`cf4r<TM^*3pQ5enPR`3M6IWB}?!<6R5vp~?_7I=J)%C8;T(^GLA~4~Rl((}1!v1o-;>$65eC1I7%XX-Qp4T6!-}pk<U|sHDPXqmVFeHW~9F7|VVGHy_2)lhBf&J_}x<q?FLE{Aaui8Nm`h6lu*0xtQFK4mC)v?>umPz0Iut?$H`R_*|b|r_zn>Py7wb8s2WIm>`4&tZ-&-9ql0W?Y;TTb=JrGd3~4W3%uUtNKW%GcR5zq92d-+*n5H?MDl7SQkLJ3tAIlRvPkC=3+M|t4h_RC$X=fHvwkUH!EK8}K2g)Qwir1$e`PdQ8s|9y5_rD&CcByDMJ|cS{ED+inP!CJ6y-yq!y}<fG7i1q)QjUJiVeiuqZ==CqWvN!CD$~ZV-Bn9qR%G<!#~Zf!X;=w24%PLIK_W=;TDh")))
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Wrong Answer

Solution code:


def lowbit(x):
	return x & (-x)

def update(n , c ,x , y):
	while x <= n:
		c[x] += y
		x += lowbit(x)

def query(c , x):
	print(len(c) , x)
	ans = 0
	while x != 0:
		ans += c[x]
		x -= lowbit(x)
	return ans

def main():
	n , q = map(int , input().split())
	a_li = list(map(int , input().split()))
	a_li.insert(0,0)
	sum_li = [0 for _ in range(n + 1)]
	for i in range(1 , n + 1):
		sum_li[i] = sum_li[i - 1] + a_li[i]

	c = [0 for _ in range(n + 1)]
	for _ in range(q):
		t , l , r = map(int , input().split())
		if t == 1:
			print(query(c , r) - query(c , l) +  sum_li[r] - sum_li[l])
		else:
			update(n , c , l + 1 , r)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class BinaryIndexTree:
    def __init__(self, n):
        self.size = n
        self._container = [0] * (n + 1)
        self.depth = n.bit_length()

    def sum(self, i):
        if i == 0:
            return 0
        s = 0
        while i > 0:
            s += self._container[i]
            i -= i & (-i)
        return s

    def add(self, i, x):
        if i == 0:
            return
        while i <= self.size:
            self._container[i] += x
            i += i & (-i)

    def lower_bound(self, x):
        if x == 0:
            return 0

        s = 0
        idx = 0
        for i in range(self.depth, -1, -1):
            k = idx + (1 << i)
            if k <= self.size and s + self._container[k] < x:
                s += self._container[k]
                idx += 1 << i
        return idx + 1

    def __repr__(self):
        return str(self._container)


def main():
    N, Q = map(int, readline().split())
    a = list(map(int, readline().split()))
    bit = BinaryIndexTree(N + 1)

    for i, x in enumerate(a, 1):
        bit.add(i, x)

    for _ in range(Q):
        a, b, c = map(int, readline().split())
        if a == 0:
            bit.add(b, c)
        else:
            b += 1
            c += 1
            print(bit.sum(c - 1) - bit.sum(b - 1))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
    
    def make(self, list):
        self.tree[1:] = list.copy()
        for i in range(self.size):
            j = i + (i & (-i))
            if j < self.size:
                self.tree[j] += self.tree[i]
 
    def sum(self, i):
        # [0, i) の要素の総和を返す
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s
    # 0 index を 1 index に変更  転倒数を求めるなら1を足していく
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    # 総和がx以上になる位置のindex をbinary search
    def bsearch(self,x):
        le = 0
        ri = 1<<(self.size.bit_length()-1)
        while ri > 0:
            if le+ri <= self.size and self.tree[le+ri]<x:
                x -= self.tree[le+ri]
                le += ri
            ri >>= 1
        return le+1

n,q = map(int,input().split())
a = list(map(int,input().split()))
bit = BIT(n)
bit.make(a)
for i in range(q):
    t,l,r = map(int,input().split())
    if t == 0:
        bit.add(l,r)
    else:
        print(bit.sum(r)-bit.sum(l))

Submission status: Wrong Answer

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10**9)
INF = 10**19
MOD = 10**9 + 7
EPS = 10**-10

class BIT:
    """ Binary Indexed Tree """

    def __init__(self, n):
        self.n = n
        # 0-indexed
        n += 1
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    def query(self, l, r):
        """ 区間和の取得 [l, r) """
        return self.sum(r-1) - self.sum(l-1)
    
    def get(self, i):
        """ 一点取得 """
        return self.query(i, i+1)

    def update(self, i, x):
        """ 値の更新：添字i, 値x """
        self.add(i, x - self.get(i))

    def print(self):
        for i in range(self.n):
            print(self.get(i), end=' ')
        print()

N, Q = MAP()
A = LIST()
bit = BIT(N)
for i in range(N):
    bit.add(i, A[i])

bit.print()

for i in range(Q):
    q, a, b = MAP()

    if q == 0:
        bit.add(a, b)
    else:
        ans = bit.query(a, b)
        print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8[:], ), cache=True)
def build(raw_data):
    bit = raw_data.copy()
    for i in range(len(bit)):
        j = i + (i & (-i))
        if j < len(bit):
            bit[j] += bit[i]
    return bit


@njit((i8[:], i8), cache=True)
def get_sum(bit, i):
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s


@njit((i8[:], i8, i8), cache=True)
def add(bit, i, x):
    while i < len(bit):
        bit[i] += x
        i += i & -i


@njit((i8[:], i8), cache=True)
def find_kth_element(bit, k):
    N = len(bit)
    x, sx = 0, 0
    dx = 1
    while 2 * dx < N:
        dx *= 2
    while dx:
        y = x + dx
        if y < N:
            sy = sx + bit[y]
            if sy < k:
                x, sx = y, sy
        dx //= 2
    return x + 1

@njit((i8[:], i8[:]), cache=True)
def main(X, TAB):
    bit = build(X)
    for i in range(0, len(TAB), 3):
        t, a, b = TAB[i:i+3]
        if t == 0:
            add(bit, a, b)
        else:
            x = get_sum(bit, b) - get_sum(bit, a)
            print(x)

N, Q = map(int, readline().split())
X = np.array([0] + readline().split(), np.int64)
TAB = np.array(read().split(), np.int64)

main(X, TAB)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
NN = 19
BIT = [0] * (2 ** NN + 1)

def addbit(i, x=1):
    while i <= 2**NN:
        BIT[i] += x
        i += i & (-i)

def getsum(i):
    ret = 0
    while i != 0:
        ret += BIT[i]
        i -= i&(-i)
    return ret

N, Q = map(int, input().split())
A = [int(a) for a in input().split()]
for i, a in enumerate(A):
    addbit(i+1, a)

for _ in range(Q):
    a, b, c = map(int, input().split())
    if a == 0:
        addbit(b, c)
    else:
        print(getsum(c) - getsum(b))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np


def read():
    return sys.stdin.buffer.readline().rstrip()


def main():
    n, q = map(int, read().split())
    a = np.array([0] + [int(i) for i in read().split()]).cumsum()
    for _ in range(q):
        query = [int(i) for i in read().split()]
        if query[0] == 0:
            a[query[1] + 1:] += query[2]
        else:
            print(a[query[2]] - a[query[1]])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np


def read():
    return sys.stdin.buffer.readline().rstrip()


def main():
    n, q = map(int, read().split())
    a = np.array([int(i) for i in read().split()])
    for _ in range(q):
        query = [int(i) for i in read().split()]
        if query[0] == 0:
            a[query[1]] += query[2]
        else:
            print(a[query[1]:query[2]].sum())


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys


def read():
    return sys.stdin.buffer.readline().rstrip()


def main():
    n, q = map(int, read().split())
    a = [int(i) for i in read().split()]
    for _ in range(q):
        query = [int(i) for i in read().split()]
        if query[0] == 0:
            a[query[1]] += query[2]
        else:
            print(sum(a[query[1]:query[2]]))


if __name__ == '__main__':
    main()