結果

問題 No.789 範囲の合計
ユーザー 双六
提出日時 2020-07-22 00:01:17
言語 PyPy3
(7.3.15)
結果
MLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,258 bytes
コンパイル時間 483 ms
コンパイル使用メモリ 82,320 KB
実行使用メモリ 157,996 KB
最終ジャッジ日時 2024-12-31 17:52:44
合計ジャッジ時間 4,621 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 8 MLE * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys; input = sys.stdin.buffer.readline
from collections import defaultdict

def getlist():
	return list(map(int, input().split()))

class SegmentTree(object):
	#N:処理する区間の長さ
	def __init__(self, N):
		self.N0 = 2 ** (N - 1).bit_length()
		self.data = [0] * (2 * self.N0)

	#k番目の値にxを足す
	def update(self, k, x):
		k += self.N0 - 1
		self.data[k] += x
		while k > 0:
			k = (k - 1) // 2
			self.data[k] = self.data[2 * k + 1] + self.data[2 * k + 2]

	#区間[l, r]の和
	def query(self, l, r):
		L = l + self.N0; R = r + self.N0 + 1
		m = 0
		while L < R:
			if R & 1:
				R -= 1
				m += self.data[R - 1]
			if L & 1:
				m += self.data[L - 1]
				L += 1
			L >>= 1; R >>= 1

		return m

#処理内容
def main():
	N = int(input())
	Q = []; S = []
	for i in range(N):
		q = getlist()
		Q.append(q)
		if q[0] == 0:
			S.append(q[1])
		else:
			S.append(q[1]); S.append(q[2])
	S = list(sorted(list(set(S))))
	# key:値 value:index
	D = defaultdict(int)
	for i in range(len(S)):
		D[S[i]] = i

	# セグ木
	ans = 0
	Seg = SegmentTree(2 * N)
	for a, b, c in Q:
		if a == 0:
			x = D[b]
			y = c
			Seg.update(x, y)
		else:
			l = D[b]
			r = D[c]
			ans += Seg.query(l, r)

	print(ans)

	
if __name__ == '__main__':
	main()
0