結果
問題 | No.2065 Sum of Min |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
class BIT:__all__ = ['add', 'sumrange', 'lower_left']def __init__(self, maxsize=10**6):assert (maxsize > 0)self._n = maxsize+1self._bitdata = [0]*(maxsize+1)def add(self, i, x):'''Add x to A[i] (A[i] += x) '''assert(0 <= i < self._n)pos = i+1while pos < self._n:self._bitdata[pos] += xpos += pos&(-pos)def running_total(self, i):''' Return sum of (A[0] ... A[i]) '''assert (-1<= i < self._n)if i == -1:return 0returnval = 0pos = i+1while pos:returnval += self._bitdata[pos]pos -= pos & (-pos)return returnvaldef 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._nreturn 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 -1pos = 0k = 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 += kk //= 2return posN,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=0ansl=[0]*Qfor 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=jbreakif j==len(C)-1:this=len(C)l-=1r-=1ansl[i]=A2.sumrange(l,r)+(B.sumrange(l,r)*x)for i in ansl:print(i)