結果

問題 No.2065 Sum of Min
ユーザー kozykozy
提出日時 2022-09-02 22:34:50
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 862 ms / 2,000 ms
コード長 2,036 bytes
コンパイル時間 305 ms
コンパイル使用メモリ 82,440 KB
実行使用メモリ 106,472 KB
最終ジャッジ日時 2024-04-27 22:11:00
合計ジャッジ時間 14,860 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
52,704 KB
testcase_01 AC 36 ms
54,084 KB
testcase_02 AC 32 ms
52,488 KB
testcase_03 AC 34 ms
54,088 KB
testcase_04 AC 488 ms
104,660 KB
testcase_05 AC 493 ms
104,676 KB
testcase_06 AC 633 ms
105,452 KB
testcase_07 AC 271 ms
106,472 KB
testcase_08 AC 640 ms
104,016 KB
testcase_09 AC 789 ms
105,452 KB
testcase_10 AC 757 ms
106,224 KB
testcase_11 AC 719 ms
106,460 KB
testcase_12 AC 762 ms
105,500 KB
testcase_13 AC 758 ms
105,828 KB
testcase_14 AC 862 ms
106,344 KB
testcase_15 AC 761 ms
105,680 KB
testcase_16 AC 791 ms
105,424 KB
testcase_17 AC 792 ms
105,828 KB
testcase_18 AC 765 ms
105,448 KB
testcase_19 AC 768 ms
105,960 KB
testcase_20 AC 762 ms
105,700 KB
testcase_21 AC 762 ms
105,440 KB
権限があれば一括ダウンロードができます

ソースコード

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