結果

問題 No.789 範囲の合計
ユーザー 双六双六
提出日時 2020-07-22 00:01:17
言語 PyPy3
(7.3.15)
結果
MLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,258 bytes
コンパイル時間 656 ms
コンパイル使用メモリ 87,148 KB
実行使用メモリ 159,592 KB
最終ジャッジ日時 2023-08-30 06:06:52
合計ジャッジ時間 5,606 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 94 ms
71,756 KB
testcase_01 AC 94 ms
71,392 KB
testcase_02 MLE -
testcase_03 AC 218 ms
99,732 KB
testcase_04 MLE -
testcase_05 MLE -
testcase_06 MLE -
testcase_07 AC 217 ms
99,136 KB
testcase_08 AC 260 ms
120,936 KB
testcase_09 AC 249 ms
117,016 KB
testcase_10 MLE -
testcase_11 MLE -
testcase_12 MLE -
testcase_13 AC 95 ms
71,444 KB
testcase_14 AC 93 ms
71,840 KB
権限があれば一括ダウンロードができます

ソースコード

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