省略
省略
C++に変換後のコードはこちら
int N, Q, A[1d5];
int L[1d5], R[1d5], X[1d5];
int ind[1d5], val[1d5], qind[1d5];
ll res[1d5];
{
int i, k;
fenwick<ll> v;
fenwick<int> c;
rd(N,Q,A(N),(ind,L--,R--,X)(Q));
v.malloc(N); v.init(N);
c.malloc(N); c.init(N);
rep(i,N) ind[i] = i, val[i] = A[i];
rep(i,Q) qind[i] = i;
sortA(N, val, ind);
sortA(Q, X, L, R, qind);
k = N-1;
for(i=Q-1;i>=0;i--){
while(k>=0 && val[k] >= X[i]){
v.add(ind[k],val[k]);
c.add(ind[k],1);
k--;
}
res[qind[i]] = v.range(L[i], R[i]) - (ll) X[i] * c.range(L[i], R[i]);
}
rep(i,Q) wt(res[i]);
}
Current time: 2024年03月30日00時26分01秒
Last modified: 2019年09月21日11時56分58秒 (by laycrs)
Tags: Competitive_Programming_Incomplete yukicoder
トップページに戻る
Logged in as: unknown user (not login)