結果
問題 | No.789 範囲の合計 |
ユーザー |
![]() |
提出日時 | 2019-04-16 01:54:17 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 832 bytes |
コンパイル時間 | 190 ms |
コンパイル使用メモリ | 82,472 KB |
実行使用メモリ | 114,536 KB |
最終ジャッジ日時 | 2024-09-22 08:09:28 |
合計ジャッジ時間 | 11,756 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 4 WA * 1 TLE * 6 -- * 4 |
ソースコード
import sysinput = sys.stdin.readlinefrom bisect import bisect_left as blN = 18X = [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 = sorted(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)