結果

問題 No.877 Range ReLU Query
ユーザー _____TAB__________TAB_____
提出日時 2020-04-19 03:05:07
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 595 ms / 2,000 ms
コード長 2,094 bytes
コンパイル時間 1,191 ms
コンパイル使用メモリ 105,220 KB
実行使用メモリ 64,972 KB
最終ジャッジ日時 2023-08-08 04:39:25
合計ジャッジ時間 7,810 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 4 ms
4,380 KB
testcase_02 AC 3 ms
4,380 KB
testcase_03 AC 4 ms
4,380 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 4 ms
4,380 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 3 ms
4,376 KB
testcase_11 AC 554 ms
51,212 KB
testcase_12 AC 482 ms
48,496 KB
testcase_13 AC 383 ms
40,608 KB
testcase_14 AC 401 ms
36,516 KB
testcase_15 AC 595 ms
62,040 KB
testcase_16 AC 576 ms
61,020 KB
testcase_17 AC 588 ms
61,620 KB
testcase_18 AC 589 ms
62,440 KB
testcase_19 AC 434 ms
64,972 KB
testcase_20 AC 511 ms
64,024 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
#include <functional>
using namespace std;

template <typename T>
struct SegmentTree{
private:
  using F = function<T(T,T)>;
  int n;
  F f;
  T ti;
  vector<T> dat;
public:
  SegmentTree(){};
  SegmentTree(F f,T ti) : f(f),ti(ti) {}
  void build(int n_){
    n = n_;
    dat.assign(2*n,ti);
  }
  void build(const vector<T> &v){
    int n_ = v.size();
    build(n_);
    for(int i = 0; i < n; ++i) dat[n+i]=v[i];
    for(int i = n-1; i >= 0; --i)
      dat[i]=f(dat[2*i+0],dat[2*i+1]);
  }
  long long query(int a,int b, long long x){
    long long ret = 0;
    for(int l = a+n, r = b+n; l < r; l >>= 1, r >>= 1){
      if(l&1) ret += dat[l++].query(x);
      if(r&1) ret += dat[--r].query(x);
    }
    return ret;
  }
};

struct value {
  vector<long long> dat;
  vector<long long> sum;
  value(){}
  value(long long x) : dat(1,x), sum(1,x) {}
  void merge(const value& rhs){
    size_t sz = dat.size();
    dat.insert(dat.end(),rhs.dat.begin(),rhs.dat.end());
    sum.insert(sum.end(),rhs.sum.begin(),rhs.sum.end());
    if(!sz) return;
    inplace_merge(dat.begin(),dat.begin()+sz,dat.end());
    sum[0] = dat[0];
    for(size_t i = 1; i < sum.size(); ++i)
      sum[i] = sum[i-1] + dat[i];
  }
  long long query(long long x){
    long long idx = upper_bound(dat.begin(), dat.end(), x) - dat.begin();
    long long sz = sum.size();
    if(idx == sz) return 0LL;
    long long ret = sum.back();
    if(idx > 0) ret -= sum[idx-1];
    ret -= (sz-idx)*x;
    return ret;
  }
};

int main(){
  int N, Q;
  cin >> N >> Q;

  vector<value> A;
  for(int i = 0; i < N; ++i){
    int a;
    cin >> a;
    A.emplace_back(a);
  }

  function<value(value,value)> f = [](value a, value b){
                                     a.merge(b);
                                     return a;
                                   };

  SegmentTree<value> st(f,value());
  st.build(A);
  
  while(Q--){
    long long t, l, r, x;
    cin >> t >> l >> r >> x;
    --l;
    if(t == 1){
      cout << st.query(l,r,x) << endl;
    }
  }
}
0