結果

問題 No.877 Range ReLU Query
コンテスト
ユーザー どらら
提出日時 2019-09-07 13:24:16
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 333 ms / 2,000 ms
コード長 2,250 bytes
コンパイル時間 2,099 ms
コンパイル使用メモリ 182,308 KB
実行使用メモリ 12,904 KB
最終ジャッジ日時 2024-11-08 10:15:39
合計ジャッジ時間 6,525 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

struct ST {
  ll x, y;
  ST():x(0),y(0){}
  ST(ll x, ll y):x(x),y(y){}
};
ST combine(const ST& lhs, const ST& rhs){
  ST st;
  st.x = lhs.x + rhs.x;
  st.y = lhs.y + rhs.y;
  return st;
}
template<class S>
class SegmentTree {
  int N;
  vector<S> t;
  void build(){
    for(int i=N-1; i>0; i--){
      t[i] = combine(t[i<<1], t[i<<1|1]);
    }
  }
public:
  SegmentTree(int n_){
    N = 1;
    while(N < n_) N *= 2;
    t.resize(2*N);
    for(int i=N; i<2*N; i++){
      t[i] = S();
    }
    build();
  }
  SegmentTree(const vector<S>& v){
    N = 1;
    while(N < v.size()) N *= 2;
    t.resize(2*N);
    for(int i=0; i<v.size(); i++){
      t[i+N] = v[i];
    }
    build();
  }
  void modify(int p, S val){
    for(t[p+=N] = val; p>>=1;){
      t[p] = combine(t[p<<1], t[p<<1|1]);
    }
  }
  S query(int l, int r){
    S resl, resr;
    for(l+=N, r+=N; l<r; l>>=1, r>>=1){
      if(l&1) resl = combine(resl, t[l++]);
      if(r&1) resr = combine(t[--r], resr);
    }
    return combine(resl, resr);
  }
};


struct X {
  int i;
  int l, r;
  ll x;
};
bool operator<(const X& a, const X& b){
  return a.x > b.x;
}

int main(){
  int N, Q;
  cin >> N >> Q;
  priority_queue<pair<ll,int>> que;
  rep(i,N){
    ll a;
    cin >> a;
    que.push(make_pair(a,i));
  }
  vector<X> query;
  rep(i,Q){
    X st;
    cin >> st.i >> st.l >> st.r >> st.x;
    st.l--;
    st.r--;
    st.i = i;
    query.push_back(st);
  }
  sort(ALLOF(query));

  vector<ll> ret(Q);
  SegmentTree<ST> segtree(N+1);
  ll sum = 0;
  ll prev = -1;
  rep(i,query.size()){
    ll x = query[i].x;

    while(true){
      if(que.empty()) break;
      pair<ll,int> p = que.top();
      if(p.first >= x){
        segtree.modify(p.second,ST(p.first,1));
        que.pop();
      }else{
        break;
      }
    }
    ST st = segtree.query(query[i].l, query[i].r+1);
    ret[query[i].i] = st.x - st.y * x;
  }

  rep(i,ret.size()){
    cout << ret[i] << endl;
  }
  
  return 0;
}
0