結果
問題 | No.789 範囲の合計 |
ユーザー |
![]() |
提出日時 | 2019-04-16 01:48:38 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 786 bytes |
コンパイル時間 | 83 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 37,472 KB |
最終ジャッジ日時 | 2024-09-22 08:08:45 |
合計ジャッジ時間 | 2,857 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 1 WA * 1 TLE * 1 -- * 12 |
ソースコード
from bisect import bisect_left as blN = 17X = [0] * (2**(N+1)-1)def add(j, x):i = 2**N + j - 1while i >= 0:X[i] += xi = (i-1) // 2def rangeof(i):s = (len(bin(i+1))-3)l = ((i+1) - (1<<s)) * (1<<N-s)r = l + (1<<N-s)return (l, r)def rangesum(a, b, i=0):l, r = rangeof(i)if l >= b or r <= a:return 0if a <= l and r <= b:return X[i]return rangesum(a, b, 2*i+1) + rangesum(a, b, 2*i+2)Q = int(input())s = 0Y = []Z = set([])for _ in range(Q):t, a, b = map(int, input().split())Y.append((t, a, b))if t == 1:Z |= set([a, b])Z = list(Z)for t, a, b in Y:if t == 0:add(bl(Z, a), b)else:s += rangesum(bl(Z, a), bl(Z, b)+1)print(s)