結果

問題 No.789 範囲の合計
ユーザー hedwig100hedwig100
提出日時 2020-05-05 18:20:08
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 975 ms / 1,000 ms
コード長 1,878 bytes
コンパイル時間 89 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 29,348 KB
最終ジャッジ日時 2024-06-26 23:49:38
合計ジャッジ時間 10,026 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 31 ms
11,136 KB
testcase_01 AC 31 ms
11,008 KB
testcase_02 AC 975 ms
28,652 KB
testcase_03 AC 596 ms
20,992 KB
testcase_04 AC 941 ms
29,348 KB
testcase_05 AC 845 ms
28,500 KB
testcase_06 AC 907 ms
28,636 KB
testcase_07 AC 620 ms
21,888 KB
testcase_08 AC 921 ms
28,872 KB
testcase_09 AC 812 ms
28,092 KB
testcase_10 AC 858 ms
27,096 KB
testcase_11 AC 677 ms
29,200 KB
testcase_12 AC 673 ms
29,204 KB
testcase_13 AC 30 ms
11,008 KB
testcase_14 AC 30 ms
11,008 KB
権限があれば一括ダウンロードができます

ソースコード

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)
            if r < len(toID) and toID[r] == c:
                r += 1
            ans += st.query(l,r)
    print(ans)
if __name__ == '__main__':
    main()
0