結果

問題 No.789 範囲の合計
ユーザー hedwig100
提出日時 2020-05-05 18:19:45
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 343 ms / 1,000 ms
コード長 1,878 bytes
コンパイル時間 378 ms
コンパイル使用メモリ 82,544 KB
実行使用メモリ 105,292 KB
最終ジャッジ日時 2024-06-26 23:48:49
合計ジャッジ時間 4,617 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

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