結果

問題 No.2065 Sum of Min
ユーザー kozy
提出日時 2022-09-02 22:34:50
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 962 ms / 2,000 ms
コード長 2,036 bytes
コンパイル時間 362 ms
コンパイル使用メモリ 82,020 KB
実行使用メモリ 106,272 KB
最終ジャッジ日時 2024-11-16 04:43:49
合計ジャッジ時間 17,801 ms
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

class BIT:
__all__ = ['add', 'sumrange', 'lower_left']
def __init__(self, maxsize=10**6):
assert (maxsize > 0)
self._n = maxsize+1
self._bitdata = [0]*(maxsize+1)
def add(self, i, x):
'''Add x to A[i] (A[i] += x) '''
assert(0 <= i < self._n)
pos = i+1
while pos < self._n:
self._bitdata[pos] += x
pos += pos&(-pos)
def running_total(self, i):
''' Return sum of (A[0] ... A[i]) '''
assert (-1<= i < self._n)
if i == -1:
return 0
returnval = 0
pos = i+1
while pos:
returnval += self._bitdata[pos]
pos -= pos & (-pos)
return returnval
def sumrange(self, lo=0, hi=None):
''' Return sum of (A[lo] ... A[hi]) '''
if lo < 0:
raise ValueError('lo must be non-negative')
if hi is None:
hi = self._n
return self.running_total(hi) - self.running_total(lo-1)
def lower_left(self, total):
''' Return min-index satisfying {sum(A0 ~ Ai) >= total}
only if Ai >= 0 (for all i)
'''
if total < 0:
return -1
pos = 0
k = 1<<(self._n.bit_length()-1)
while k > 0:
if pos+k < self._n and self._bitdata[pos+k] < total:
total -= self._bitdata[pos+k]
pos += k
k //= 2
return pos
N,Q=map(int,input().split())
A=list(map(int,input().split()))
A2=BIT(N)
for i in range(N):
A2.add(i,A[i])
B=BIT(N)
q=list()
for _ in range(Q):
l,r,x=map(int,input().split())
q.append([x,l,r,_])
q.sort(reverse=True)
C=list()
for i in range(N):
C.append([A[i],i])
C.sort(reverse=True)
this=0
ansl=[0]*Q
for x,l,r,i in q:
for j in range(this,len(C)):
a,ind=C[j]
if a>=x:
A2.add(ind,-A[ind])
B.add(ind,1)
else:
this=j
break
if j==len(C)-1:
this=len(C)
l-=1
r-=1
ansl[i]=A2.sumrange(l,r)+(B.sumrange(l,r)*x)
for i in ansl:
print(i)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0