結果

問題 No.789 範囲の合計
ユーザー hedwig100hedwig100
提出日時 2020-05-05 18:16:18
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
RE  
実行時間 -
コード長 1,812 bytes
コンパイル時間 248 ms
コンパイル使用メモリ 10,816 KB
実行使用メモリ 26,708 KB
最終ジャッジ日時 2023-09-09 06:34:10
合計ジャッジ時間 6,506 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 AC 17 ms
8,192 KB
testcase_02 RE -
testcase_03 AC 506 ms
18,220 KB
testcase_04 RE -
testcase_05 WA -
testcase_06 RE -
testcase_07 AC 512 ms
19,100 KB
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 WA -
testcase_13 AC 17 ms
8,092 KB
testcase_14 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
from bisect import bisect_left

class SegmentTree():
    f = lambda self,x,y:x + y
    unit = 0
   
    def __init__(self,array):
        self.N = len(array)
        self.tree = [self.unit] * (2*self.N)
        #self._build(array)
    
    def _build(self,array):
        for i,x in enumerate(array,self.N):
            self.tree[i] = x
        for i in range(self.N - 1,0,-1):
            self.tree[i] = self.f(self.tree[i << 1],self.tree[i << 1|1])
    
    def update(self,k,x):
        k += self.N
        self.tree[k] = x
        while k > 1:
            k >>= 1
            self.tree[k] = self.f(self.tree[k << 1],self.tree[k << 1|1])
    
    def query(self,l,r):
        l += self.N
        r += self.N
        vl = self.unit
        vr = self.unit
        while l < r:
            if l&1: 
                vl = self.f(vl,self.tree[l])
                l += 1
            if r&1:
                r -= 1
                vr = self.f(self.tree[r],vr)
            l >>= 1
            r >>= 1
        return self.f(vl,vr)
    
    def __str__(self):
        return '\n'.join(' '.join(str(v) for v in self.tree[1<<i:1<<(i + 1)]) for i in range((2*self.N).bit_length()))


def main():
    N = int(input())
    Q = [tuple(map(int,input().split())) for _ in range(N)]
    value = [b for a,b,c in Q if a == 0]
    toID = sorted(list(set(value)))
    st = SegmentTree([0] * len(value))
    ans = 0
    for a,b,c in Q:
        if a == 0:
            i = bisect_left(toID,b)
            before = st.query(i,i + 1)
            new = before + c
            st.update(i,new)
        else:
            l = bisect_left(toID,b)
            r = bisect_left(toID,c)
            ans += st.query(l,r + 1)
    print(ans)
if __name__ == '__main__':
    main()
0