結果
問題 | No.789 範囲の合計 |
ユーザー | titia |
提出日時 | 2019-02-08 22:55:50 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,169 bytes |
コンパイル時間 | 95 ms |
コンパイル使用メモリ | 11,076 KB |
実行使用メモリ | 51,492 KB |
最終ジャッジ日時 | 2023-09-14 03:54:04 |
合計ジャッジ時間 | 12,977 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 16 ms
8,332 KB |
testcase_01 | AC | 16 ms
8,188 KB |
testcase_02 | TLE | - |
testcase_03 | AC | 498 ms
23,808 KB |
testcase_04 | TLE | - |
testcase_05 | TLE | - |
testcase_06 | TLE | - |
testcase_07 | AC | 374 ms
24,140 KB |
testcase_08 | AC | 773 ms
37,300 KB |
testcase_09 | AC | 759 ms
36,732 KB |
testcase_10 | TLE | - |
testcase_11 | TLE | - |
testcase_12 | TLE | - |
testcase_13 | AC | 16 ms
8,332 KB |
testcase_14 | AC | 16 ms
8,204 KB |
ソースコード
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=sorted(list(set(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)