結果
問題 | No.2065 Sum of Min |
ユーザー | flygon |
提出日時 | 2022-09-19 01:37:42 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,237 ms / 2,000 ms |
コード長 | 1,091 bytes |
コンパイル時間 | 398 ms |
コンパイル使用メモリ | 86,744 KB |
実行使用メモリ | 176,680 KB |
最終ジャッジ日時 | 2023-08-23 18:31:32 |
合計ジャッジ時間 | 20,488 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 79 ms
87,608 KB |
testcase_01 | AC | 78 ms
87,592 KB |
testcase_02 | AC | 80 ms
87,352 KB |
testcase_03 | AC | 79 ms
87,564 KB |
testcase_04 | AC | 690 ms
174,680 KB |
testcase_05 | AC | 653 ms
173,508 KB |
testcase_06 | AC | 806 ms
129,764 KB |
testcase_07 | AC | 430 ms
121,304 KB |
testcase_08 | AC | 814 ms
130,460 KB |
testcase_09 | AC | 983 ms
175,992 KB |
testcase_10 | AC | 810 ms
171,820 KB |
testcase_11 | AC | 787 ms
171,952 KB |
testcase_12 | AC | 1,087 ms
175,964 KB |
testcase_13 | AC | 1,091 ms
175,732 KB |
testcase_14 | AC | 1,117 ms
176,128 KB |
testcase_15 | AC | 1,085 ms
175,624 KB |
testcase_16 | AC | 1,086 ms
176,680 KB |
testcase_17 | AC | 1,079 ms
176,036 KB |
testcase_18 | AC | 1,115 ms
175,908 KB |
testcase_19 | AC | 1,237 ms
175,420 KB |
testcase_20 | AC | 1,084 ms
176,160 KB |
testcase_21 | AC | 1,129 ms
176,588 KB |
ソースコード
n,q = map(int,input().split()) a = list(map(int,input().split())) qs = [] for i in range(q): l,r,x = map(int,input().split()) qs.append((l-1,x,i,-1)) qs.append((r,x,i,1)) qs.sort(key = lambda x:x[0]) def compress(arr): *s, = set(arr) return {num: i for i,num in enumerate(sorted(s))} ca = compress(a) sa = sorted(set(a)) seg_len = 1<<19 # > 5*(10**5) seg = [0]*(2*seg_len) seg2 = [0]*(2*seg_len) def update(pos,x,seg): pos += seg_len seg[pos] += x while True: pos >>= 1 if not pos: break seg[pos] = seg[pos<<1] + seg[pos<<1|1] def get_query(l,r,seg): l += seg_len; r += seg_len res = 0 while l < r: if l & 1: res += seg[l] l += 1 if r & 1: r -= 1 res += seg[r] l >>= 1; r >>= 1 return res now = 0 ans =[0]*q from bisect import bisect_left, bisect_right for l,x,i,ki in qs: while now < l: update(ca[a[now]], 1, seg) update(ca[a[now]], a[now], seg2) now += 1 xx = bisect_right(sa,x) s = get_query(0, xx, seg2) t = get_query(0, xx, seg) ans[i] += ki*(s+(l-t)*x) print(*ans, sep = "\n")