結果

問題 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)
0