結果
問題 | No.2065 Sum of Min |
ユーザー |
![]() |
提出日時 | 2022-09-02 22:02:46 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 786 ms / 2,000 ms |
コード長 | 1,743 bytes |
コンパイル時間 | 283 ms |
コンパイル使用メモリ | 82,032 KB |
実行使用メモリ | 136,936 KB |
最終ジャッジ日時 | 2024-11-16 03:30:29 |
合計ジャッジ時間 | 15,059 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
from bisect import bisect_leftfrom operator import addclass SegmentTree():def __init__(self, n, unit, f, A=None):self.s = 2**(n-1).bit_length()self.size = 2*self.sself.node = [unit]*self.sizeself.op = fself.UNIT = unitif A:for i in range(n):self.node[self.s+i] = A[i]for i in range(self.s-1, -1, -1):self.node[i] = self.op(self.node[2*i], self.node[2*i+1])def update(self, i, v):i += self.sself.node[i] = vwhile i > 0:i >>= 1self.node[i] = self.op(self.node[2*i], self.node[2*i+1])def get(self, l, r):vl, vr = self.UNIT, self.UNITl += self.sr += self.swhile l < r:if l & 1:vl = self.op(self.node[l], vl)l += 1if r & 1:r -= 1vr = self.op(vr, self.node[r])l >>= 1r >>= 1return self.op(vl, vr)N, Q = map(int, input().split())A = list(map(int, input().split()))B = [list(map(int, input().split())) for _ in range(Q)]X = [b[2] for b in B]X.sort()M = len(X)Y = [[] for _ in range(M+1)]Z = [[] for _ in range(M)]for i in range(Q):l, r, x = B[i]l -= 1ind = bisect_left(X, x)Z[ind].append([i, l, r])for i, a in enumerate(A):ind = bisect_left(X, a)Y[ind].append([i, a])st1 = SegmentTree(N, 0, add)st2 = SegmentTree(N, 0, add, [1]*N)ans = [0]*Qfor i in range(M):for ind, a in Y[i]:st1.update(ind, a)st2.update(ind, 0)x = X[i]for ind, l, r in Z[i]:ans[ind] = st1.get(l, r)+st2.get(l, r)*xprint(*ans, sep='\n')