yukicoder No.877 - Range ReLU Query

Source

ニコニコミュニティ
問題文

問題概要

省略

解法

省略

cLayversion 20190921-1)のコード

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)

ログイン: