結果

問題 No.1000 Point Add and Array Add
コンテスト
ユーザー Kiri8128
提出日時 2020-02-28 22:23:51
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 383 ms / 2,000 ms
コード長 675 bytes
コンパイル時間 221 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 130,516 KB
最終ジャッジ日時 2024-10-13 17:55:07
合計ジャッジ時間 5,864 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

NN = 18
BIT = [0] * (2**NN+1)
 
def addrange(l0, r0, x=1):
    l, r = l0, r0
    while l <= 2**NN:
        BIT[l] += x
        l += l & (-l)
    while r <= 2**NN:
        BIT[r] -= x
        r += r & (-r)
def getvalue(r):
    a = 0
    while r != 0:
        a += BIT[r]
        r -= r&(-r)
    return a

N, Q = map(int, input().split())
A = [int(a) for a in input().split()]
X = []
for _ in range(Q):
    c, x, y = input().split()
    x, y = int(x), int(y)
    X.append((c, x, y))

ans = [0] * N
for c, x, y in X[::-1]:
    if c == "A":
        ans[x-1] += getvalue(x) * y
    else:
        addrange(x, y+1)

for i in range(N):
    ans[i] += getvalue(i+1) * A[i]

print(*ans)
0