結果
問題 | No.789 範囲の合計 |
ユーザー | titia |
提出日時 | 2019-02-08 23:02:41 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 1,158 bytes |
コンパイル時間 | 253 ms |
コンパイル使用メモリ | 86,908 KB |
実行使用メモリ | 152,500 KB |
最終ジャッジ日時 | 2023-09-14 03:55:10 |
合計ジャッジ時間 | 7,617 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 65 ms
71,520 KB |
testcase_01 | AC | 65 ms
71,304 KB |
testcase_02 | MLE | - |
testcase_03 | AC | 263 ms
88,972 KB |
testcase_04 | MLE | - |
testcase_05 | MLE | - |
testcase_06 | MLE | - |
testcase_07 | TLE | - |
testcase_08 | AC | 307 ms
113,012 KB |
testcase_09 | AC | 273 ms
109,240 KB |
testcase_10 | MLE | - |
testcase_11 | MLE | - |
testcase_12 | MLE | - |
testcase_13 | AC | 62 ms
71,424 KB |
testcase_14 | AC | 64 ms
71,480 KB |
ソースコード
import sys input = sys.stdin.readline n=int(input()) Q=[list(map(int,input().split())) for i in range(n)] LIST=set() for x,a,b in Q: if x==0: LIST.add(a) else: LIST.add(a) LIST.add(b) LIST=sorted(list(LIST)) 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)