結果
| 問題 | No.1000 Point Add and Array Add |
| ユーザー |
 None
|
| 提出日時 | 2021-02-27 01:17:47 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 12,410 bytes |
| コンパイル時間 | 265 ms |
| コンパイル使用メモリ | 82,688 KB |
| 実行使用メモリ | 110,476 KB |
| 最終ジャッジ日時 | 2024-10-02 16:47:34 |
| 合計ジャッジ時間 | 7,928 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
ソースコード
class Bit:
def __init__(self, n, array=[]):
"""
:param n: number of elements
"""
self.n = n
self.tree = [0]*(n+1)
self.depth = n.bit_length() - 1
for i, a in enumerate(array):
self.add(i, a)
def get(self,i):
""" return summation of elements in [0,i) """
s = 0
i -= 1
while i >= 0:
s += self.tree[i]
i = (i & (i + 1) )- 1
return s
def build(self, array):
""" bulid BIT from array """
for i, a in enumerate(array):
self.add(i, a)
def add(self, i, x):
""" add x to i-th element """
while i < self.n:
self.tree[i] += x
i |= i + 1
def get_range(self,i,j):
""" return summation of elements in [i,j) """
if i == 0:
return self.get(j)
return self.get(j)-self.get(i)
def lower_bound(self, x, equal=False):
"""
return tuple = (return maximum i s.t. a0+a1+...+ai < x (if not existing, -1 ) , a0+a1+...+ai )
if one wants to include equal (i.e., a0+a1+...+ai <= x), please set equal = True
(Cation) We must assume that A_i>=0
"""
sum_ = 0
pos = -1 # 1-indexed の時は pos = 0
if not equal:
for i in range(self.depth, -1, -1):
k = pos + (1 << i)
if k < self.n and sum_ + self.tree[k] < x: # 1-indexed の時は k <= self.n
sum_ += self.tree[k]
pos += 1 << i
if equal:
for i in range(self.depth, -1, -1):
k = pos + (1 << i)
if k < self.n and sum_ + self.tree[k] <= x: # 1-indexed の時は k <= self.n
sum_ += self.tree[k]
pos += 1 << i
return pos, sum_
def __getitem__(self, i):
""" [a0, a1, a2, ...] """
if i<0: i=self.n+i
return self.get_range(i,i+1)
def __iter__(self):
""" [a0, a1, a2, ...] """
for i in range(self.n):
yield self.get_range(i,i+1)
def __str__(self):
text1 = " ".join(["element: "] + list(map(str, self)))
text2 = " ".join(["cumsum(1-indexed): "]+list(str(self.get(i)) for i in range(1,self.n+1)))
return "\n".join((text1, text2))
class BitImos:
def __init__(self, n, array=[]):
self.n = n
self.p = Bit(self.n + 1)
self.q = Bit(self.n + 1)
for i, a in enumerate(array):
self.add(i, a)
def add(self, s, x):
self.add_range(s,s+1,x)
def add_range(self, s, t, x):
""" add x to a close-interval [s,t)"""
self.p.add(s, -x * s)
self.p.add(t, x * t)
self.q.add(s, x)
self.q.add(t, -x)
def build(self, array):
""" bulid BIT from array """
for i, a in enumerate(array):
self.add(i, a)
def get(self,s):
return self.get_range(s,s+1)
def get_range(self,s,t):
""" return summation of elements in [s,t) """
return self.p.get(t)+self.q.get(t)*t-self.p.get(s)-self.q.get(s)*s
def __getitem__(self, s):
""" return s-th element of array (not sum-array) """
return self.q.get(s+1)
def __iter__(self):
""" max(self) returns what we obtain by the Imos method"""
for t in range(self.n):
yield self.q.get(t+1)
def __str__(self):
text1 = " ".join(["element: "] + list(map(str, self)))
return text1
class SortedList:
def __init__(self, n, A=[]):
"""
:param n: miximum value of A
self.size: number of elements in BitSet
"""
self.n = n
self.p = Bit(self.n + 1)
self.size = 0
self.flip = 0
for a in A:
self.add(a)
def add(self,x):
self.p.add(x, 1)
self.size += 1
self.flip += self.size - self.p.get(x+1) # we can remove this if we do not use flip_number
def remove(self,x):
self.p.add(x, -1)
self.size -= 1
def bisect_left(self,x):
""" return bisect_left(sorted(B),x) """
if x <= self.n:
return self.p.get(x)
else:
return self.size
def bisect_right(self,x):
""" return bisect_right(sorted(B),x) """
x += 1
if x <= self.n:
return self.p.get(x)
else:
return self.size
def flip_counter(self):
return self.flip
def count(self,x):
return self.p[x]
def count_range(self,l,r):
""" return number of elements in closed set [l,r]"""
return self.bisect_right(r)-self.bisect_left(l)
def minimum(self,k=1):
""" return k-th minimum value """
if k <= self.size:
return self.p.lower_bound(k)[0] + 1
else:
sys.stderr.write("minimum: list index out of range (k={0})\n".format(k))
def min(self):
return self.minimum(1)
def max(self):
return self.p.lower_bound(self.size)[0] + 1
def upper_bound(self,x,equal=False):
""" return maximum element lower than x """
k = self.p.get(x+equal)
if k:
return self.minimum(k)
else:
sys.stderr.write("upper_bound: no element smaller than {0} in this BitSet\n".format(x))
def lower_bound(self,x,equal=False):
""" return minimum element greater than x """
k =self.p.get(x+1-equal)+1
if k <= self.size:
return self.minimum(k)
else:
sys.stderr.write("lower_bound: no element larger than {0} in this BitSet\n".format(x))
def __getitem__(self, k):
"""
return k-th minimum element (0-indexed)
B[k] = sorted(A)[k]
"""
if len(self)==0:
sys.stderr.write("__getitem__: no elements exist in this BitSet\n")
elif k >= len(self):
sys.stderr.write("__getitem__: index (={0}) is larger than the maximum index (={1})\n".format(k,len(self)-1))
elif k >= 0:
return self.minimum(k+1)
else:
sys.stderr.write("__getitem__: index (={0}) is negative \n".format(k))
def __len__(self):
return self.size
def __iter__(self):
""" return sorted list """
for i in range(self.n+1):
if self.p[i]:
for _ in range(self.p[i]):
yield i
def __str__(self):
""" return sorted list """
text1 = " ".join(list(map(str, self)))
return "[" + text1 + "]"
class SortedList2:
""" if we need compress """
def __init__(self, data, A=[]):
"""
self.size: number of elements in BitSet
"""
self.data = sorted(list(set(data)))
self.n = len(self.data)
self.p = Bit(self.n + 1)
self.size = 0
self.flip = 0
self.code = {}
self.decode = []
for i, b in enumerate(self.data):
self.code[b] = i
self.decode.append(b)
for a in A:
self.add(a)
def add(self,x):
self.p.add(self.code[x], 1)
self.size += 1
self.flip += self.size - self.p.get(self.code[x]+1) # we can remove this if we do not use flip_number
def remove(self,x):
self.p.add(self.code[x], -1)
self.size -= 1
def bisect_left(self,x):
""" return bisect_left(sorted(B),x) """
if x in self.code.keys():
return self.p.get(self.code[x])
else:
return self.p.get(bisect_right(self.data,x))
def bisect_right(self,x):
""" return bisect_right(sorted(B),x) """
x += 1
if x in self.code.keys():
return self.p.get(self.code[x])
else:
return self.p.get(bisect_right(self.data,x))
def count(self,x):
return self.p[self.code[x]]
def count_range(self,l,r):
""" return number of elements in closed set [l,r]"""
return self.bisect_right(r)-self.bisect_left(l)
def minimum(self,k=1):
""" return k-th minimum value """
if k <= self.size:
return self.decode[self.p.lower_bound(k)[0] + 1]
else:
sys.stderr.write("minimum: list index out of range (k={0})\n".format(k))
def min(self):
return self.minimum(1)
def max(self):
return self.decode[self.p.lower_bound(self.size)[0] + 1]
def upper_bound(self,x,equal=False):
""" return maximum element lower than x """
if x in self.code.keys():
y = self.code[x] + equal
else:
y = bisect_right(self.data, x)
k = self.p.get(y)
if k:
return self.minimum(k)
else:
sys.stderr.write("upper_bound: no element smaller than {0} in this BitSet\n".format(x))
def lower_bound(self,x,equal=False):
""" return minimum element greater than x """
if x in self.code.keys():
y = self.code[x] + 1 - equal
else:
y = bisect_left(self.data, x)
k =self.p.get(y)+1
if k <= self.size:
return self.minimum(k)
else:
sys.stderr.write("lower_bound: no element larger than {0} in this BitSet\n".format(x))
def nearest(self,x,k):
""" return k-th nearest value to x """
if k>len(self):
sys.stderr.write("nearest: k (= {0}) is larger than the size of this BitSet\n".format(k))
return
def test(d):
r=self.bisect_right(x+d)-1
l=self.bisect_left(x-d)
return r-l+1<=k
ok,ng=0,10**18+1
while abs(ok-ng)>1:
mid=(ok+ng)//2
if test(mid):
ok=mid
else:
ng=mid
d=ok
r=self.bisect_right(x+d)-1
l=self.bisect_left(x-d)
if d==0:
R=self.lower_bound(x,equal=True)
L=self.upper_bound(x,equal=True)
if abs(x-L)==abs(R-x):
if self.count(L)>=k: return L
else: return R
elif abs(x-L)<abs(R-x): return L
else: return R
elif r-l+1==k:
R=self[r]
L=self[l]
if abs(x-L)<=abs(R-x): return R
else: return L
else:
if l<=0: return self[r+1]
elif r>=len(self)-1: return self[l-1]
else:
R=self[r+1]
L=self[l-1]
if abs(x-L)==abs(R-x):
if self.count(L)>=k-(r-l+1):
return L
else: return R
elif abs(x-L)<abs(R-x): return L
else: return R
def __getitem__(self, k):
"""
return k-th minimum element (0-indexed)
B[k] = sorted(A)[k]
"""
if len(self)==0:
sys.stderr.write("__getitem__: no elements exist in this BitSet\n")
elif k >= len(self):
sys.stderr.write("__getitem__: index (={0}) is larger than the maximum index (={1})\n".format(k,len(self)-1))
elif k >= 0:
return self.minimum(k+1)
else:
sys.stderr.write("__getitem__: index (={0}) is negative \n".format(k))
def __len__(self):
return self.size
def __iter__(self):
""" return sorted list """
for i in range(self.n+1):
if self.p[i]:
for _ in range(self.p[i]):
yield self.decode[i]
def __str__(self):
""" return sorted list """
text1 = " ".join(list(map(str, self)))
return "[" + text1 + "]"
###################################################
def example():
global input
example = iter(
"""
6
10 5 1 5 10 7
"""
.strip().split("\n"))
input = lambda: next(example)
###################################################
import sys
input = sys.stdin.readline
from bisect import bisect_left, bisect_right
# example()
N,Q=map(int, input().split())
A=list(map(int, input().split()))
B=BitImos(N)
res=[0]*N
for _ in range(Q):
c,x,y=input().split()
x,y=int(x),int(y)
if c=="B":
B.add_range(x-1,y,1)
else:
i=x-1
cnt=B[i]
res[i]+=cnt*A[i]
B.add(i,-B[i])
A[i]+=y
for i,b in enumerate(B):
res[i]+=b*A[i]
print(res)