結果
| 問題 |
No.789 範囲の合計
|
| コンテスト | |
| ユーザー |
 Fuyuru
|
| 提出日時 | 2024-02-16 18:43:48 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,850 bytes |
| コンパイル時間 | 677 ms |
| コンパイル使用メモリ | 81,980 KB |
| 実行使用メモリ | 126,844 KB |
| 最終ジャッジ日時 | 2024-09-28 19:35:09 |
| 合計ジャッジ時間 | 3,336 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 2 TLE * 1 -- * 12 |
ソースコード
import sys
input = sys.stdin.readline
#print = sys.stdout.write
import random
random.seed()
class RBSTmap:
def __init__(self):
self.root = None
def get_size(self):
if not self.root:
return 0
return self.root[3]
# find a node with a key x
def find(self,x):
node = self.root
while node:
v = node[2]
if v == x:
return 1
node = node[v < x]
return 0
# find the k-th key in a tree
def at(self,k):
node = self.root
k += 1
while 1:
v = (node[0][3]+1 if node[0] else 1)
if v == k:
return node[2]
if k < v:
node = node[0]
else:
k -= v
node = node[1]
def __getitem__(self,key):
node = self.root
while node:
v = node[2]
if v == key:
return node[4]
node = node[v < key]
def __setitem__(self,key,val):
node = self.root
while node:
v = node[2]
if v == key:
node[4] = val
return
node = node[v < key]
# insert a node with a key x
def insert(self,x,val):
# before insert(x), the tree must not contain a key x
rand = random.random
new_node = [None,None,x,1,val]
if not self.root:
self.root = new_node
return
node = self.root
prv = None
while node:
if node[3] == int(rand()*(node[3]+1)):
break
node[3] += 1
prv = node
node = node[node[2] < x]
if prv:
prv[prv[2] < x] = new_node
else:
self.root = new_node
left = right = new_node
st = []
while node:
st.append(node)
if node[2] < x:
left[1] = left = node
node = node[1]
else:
right[0] = right = node
node = node[0]
left[1] = right[0] = None
new_node[0],new_node[1] = new_node[1],new_node[0]
st.reverse()
for node in st:
l,r = node[:2]
node[3] = (l[3] if l else 0)+(r[3] if r else 0)+1
l,r = new_node[:2]
new_node[3] = (l[3] if l else 0)+(r[3] if r else 0)+1
# remove a node with key x
def remove(self,x):
# before remove(x), the tree must contain a key x
rand = random.random
node = self.root
prt = None
while node[2] != x:
node[3] -= 1
prt = node
node = node[node[2] < x]
cur = top = prt
if prt:
prv_d = (prt[1] == node)
else:
cur = top = [None]
prv_d = 0
left,right = node[:2]
st = [];
push = st.append
while left and right:
a = left[3];
b = right[3]
if int(rand()*(a+b)) < a:
push(left)
cur[prv_d] = cur = left
left = left[1]
prv_d = 1
else:
push(right)
cur[prv_d] = cur = right
right = right[0]
prv_d = 0
rest = left or right
cur[prv_d] = rest
if not prt:
self.root = top[0]
st.reverse()
for node in st:
l,r = node[:2]
node[3] = (l[3] if l else 0)+(r[3] if r else 0)+1
# pop the k-th key
def pop(self,k):
# when pop(x), the tree should contain the k-th element
rand = random.random
node = self.root
prt = None
k += 1
while 1:
l = node[0]
v = (l[3]+1 if l else 1)
if v == k:
break
prt = node
node[3] -= 1
if k < v:
node = node[0]
else:
k -= v
node = node[1]
r_node = node
cur = top = prt
if prt:
prv_d = (prt[1] == node)
else:
cur = top = [None]
prv_d = 0
left,right = node[:2]
st = [];
push = st.append
while left and right:
a = left[3];
b = right[3]
if int(rand()*(a+b)) < a:
push(left)
cur[prv_d] = cur = left
left = left[1]
prv_d = 1
else:
push(right)
cur[prv_d] = cur = right
right = right[0]
prv_d = 0
rest = left or right
cur[prv_d] = rest
if not prt:
self.root = top[0]
st.reverse()
for node in st:
l,r = node[:2]
node[3] = (l[3] if l else 0)+(r[3] if r else 0)+1
return r_node[2]
def print_all(self):
for i in range(self.get_size()):
print(self.at(i),self[self.at(i)])
class BIT:
def __init__(self,N):
self.N = N
self.data = RBSTmap()
def add(self,i,x):
i += 1
while i <= self.N:
if self.data.find(i):
self.data[i] = self.data[i]+x
else:
self.data.insert(i,x)
i += i&-i
def fold(self,l,r):
res = 0
while r > 0:
if self.data.find(r):
res += self.data[r]
r -= r&-r
while l > 0:
if self.data.find(l):
res -= self.data[l]
l -= l&-l
return res
bit = BIT(1000000001)
Q = int(input())
ans = 0
for _ in range(Q):
op,x,y = map(int,input().split())
if op == 0:
bit.add(x,y)
else:
ans += bit.fold(x,y+1)
print(ans)