結果

問題 No.789 範囲の合計
ユーザー hedwig100hedwig100
提出日時 2020-05-05 18:19:45
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 392 ms / 1,000 ms
コード長 1,878 bytes
コンパイル時間 880 ms
コンパイル使用メモリ 87,164 KB
実行使用メモリ 106,800 KB
最終ジャッジ日時 2023-09-09 06:38:01
合計ジャッジ時間 6,300 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 70 ms
71,448 KB
testcase_01 AC 72 ms
71,232 KB
testcase_02 AC 380 ms
102,152 KB
testcase_03 AC 310 ms
93,956 KB
testcase_04 AC 392 ms
104,544 KB
testcase_05 AC 324 ms
101,440 KB
testcase_06 AC 327 ms
103,024 KB
testcase_07 AC 288 ms
95,380 KB
testcase_08 AC 327 ms
106,800 KB
testcase_09 AC 314 ms
104,768 KB
testcase_10 AC 377 ms
96,176 KB
testcase_11 AC 310 ms
104,692 KB
testcase_12 AC 315 ms
104,624 KB
testcase_13 AC 75 ms
71,192 KB
testcase_14 AC 71 ms
71,268 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