結果

問題 No.2065 Sum of Min
ユーザー kozykozy
提出日時 2022-09-02 22:34:50
言語 PyPy3
(7.3.13)
結果
AC  
実行時間 960 ms / 2,000 ms
コード長 2,036 bytes
コンパイル時間 282 ms
コンパイル使用メモリ 87,284 KB
実行使用メモリ 108,848 KB
最終ジャッジ日時 2023-08-10 04:50:53
合計ジャッジ時間 18,564 ms
ジャッジサーバーID
(参考情報)
judge15 / judge11
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 70 ms
71,476 KB
testcase_01 AC 68 ms
71,684 KB
testcase_02 AC 69 ms
71,364 KB
testcase_03 AC 70 ms
71,444 KB
testcase_04 AC 616 ms
106,860 KB
testcase_05 AC 606 ms
106,768 KB
testcase_06 AC 761 ms
106,884 KB
testcase_07 AC 348 ms
108,848 KB
testcase_08 AC 770 ms
106,860 KB
testcase_09 AC 922 ms
106,568 KB
testcase_10 AC 911 ms
106,804 KB
testcase_11 AC 895 ms
106,452 KB
testcase_12 AC 935 ms
106,504 KB
testcase_13 AC 932 ms
106,336 KB
testcase_14 AC 960 ms
106,572 KB
testcase_15 AC 946 ms
106,396 KB
testcase_16 AC 944 ms
106,136 KB
testcase_17 AC 947 ms
106,676 KB
testcase_18 AC 947 ms
106,440 KB
testcase_19 AC 948 ms
106,576 KB
testcase_20 AC 916 ms
106,864 KB
testcase_21 AC 931 ms
106,656 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