結果

問題 No.789 範囲の合計
ユーザー titiatitia
提出日時 2019-02-08 22:24:21
言語 PyPy3
(7.3.15)
結果
MLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,157 bytes
コンパイル時間 168 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 132,996 KB
最終ジャッジ日時 2024-07-01 11:36:46
合計ジャッジ時間 9,217 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
52,096 KB
testcase_01 AC 38 ms
52,096 KB
testcase_02 MLE -
testcase_03 AC 642 ms
103,280 KB
testcase_04 AC 703 ms
123,772 KB
testcase_05 MLE -
testcase_06 AC 846 ms
127,876 KB
testcase_07 AC 524 ms
100,796 KB
testcase_08 AC 600 ms
111,696 KB
testcase_09 AC 524 ms
110,056 KB
testcase_10 TLE -
testcase_11 AC 729 ms
123,912 KB
testcase_12 AC 735 ms
124,396 KB
testcase_13 AC 39 ms
53,568 KB
testcase_14 AC 38 ms
51,712 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

n=int(input())
Q=[list(map(int,input().split())) for i in range(n)]

LIST=[]
for x,a,b in Q:
    if x==0:
        LIST.append(a)
    else:
        LIST.append(a)
        LIST.append(b)

LIST.sort()
N=len(LIST)
DICT=dict()

for i in range(N):
    DICT[LIST[i]]=i
    


for i in range(30):#要素数以上の2のベキを見つける
    if N<=2**i:
        seg_el=2**i#Segment treeの台の要素数
        break

SEG=[0]*(2*seg_el-1)#Segment treeを一次元リストとして作る

def update(n,x,seg_el):#A[n]=xに更新（反映）
    i=n+seg_el-1
    while i>=0:
        SEG[i]+=x
        i=(i-1)//2

def getvalues(a,b,k,l,r):
    if r<=a or b<=l:
        return 0
    if a<=l and r<=b:#区間[a,b)が対象区間の中にあればSEG[k]を出力
        return SEG[k]
    vl=getvalues(a,b,k*2+1,l,(l+r)//2)#それ以外のときは,SEG[k*2+1]とSEG[k*2+2]で場合分け（木の子ノード二つを見る）
    vr=getvalues(a,b,k*2+2,(l+r)//2,r)
    return vl+vr

ANS=0
for x,a,b in Q:
    if x==0:
        update(DICT[a],b,seg_el)
    else:
        ANS+=getvalues(DICT[a],DICT[b]+1,0,0,seg_el)

print(ANS)
0