#376659 (C++14) No.877 Range ReLU Query

提出ソース
結果

問題	No.877 Range ReLU Query
ユーザー	NyaanNyaan
提出日時	2019-09-06 22:46:58
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	9,710 bytes
コンパイル時間	2,131 ms
コンパイル使用メモリ	187,444 KB
実行使用メモリ	324,864 KB
最終ジャッジ日時	2024-06-24 20:19:05
合計ジャッジ時間	17,544 ms
ジャッジサーバーID （参考情報）	judge3 / judge1
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	WA	-
testcase_02	RE	-
testcase_03	RE	-
testcase_04	RE	-
testcase_05	WA	-
testcase_06	RE	-
testcase_07	RE	-
testcase_08	RE	-
testcase_09	RE	-
testcase_10	WA	-
testcase_11	RE	-
testcase_12	RE	-
testcase_13	RE	-
testcase_14	RE	-
testcase_15	RE	-
testcase_16	RE	-
testcase_17	RE	-
testcase_18	RE	-
testcase_19	RE	-
testcase_20	RE	-
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>
#define whlie while
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define rep(i,N) for(int i = 0; i < (N); i++)
#define repr(i,N) for(int i = (N) - 1; i >= 0; i--)
#define rep1(i,N) for(int i = 1; i <= (N) ; i++)
#define repr1(i,N) for(int i = (N) ; i > 0 ; i--)
#define each(x,v) for(auto& x : v)
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define vrep(v,it) for(auto it = v.begin(); it != v.end(); it++)
#define vrepr(v,it) for(auto it = v.rbegin(); it != v.rend(); it++)
#define ini(...) int __VA_ARGS__; in(__VA_ARGS__)
#define inl(...) ll __VA_ARGS__; in(__VA_ARGS__)
#define ins(...) string __VA_ARGS__; in(__VA_ARGS__)
using namespace std; void solve();
using ll = long long; using vl = vector<ll>;
using vi = vector<int>; using vvi = vector< vector<int> >;
constexpr int inf = 1001001001;
constexpr ll infLL = (1LL << 61) - 1;
struct IoSetupNya {IoSetupNya() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(7);} } iosetupnya;
template<typename T, typename U> inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; }
template<typename T, typename U> inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; }
template<typename T, typename U> ostream& operator <<(ostream& os, const pair<T, U> &p) { os << p.first << " " << p.second; return os; }
template<typename T, typename U> istream& operator >>(istream& is, pair<T, U> &p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator <<(ostream& os, const vector<T> &v) { int s = (int)v.size(); rep(i,s) os << (i ? " " : "") << v[i]; return os; }
template<typename T> istream& operator >>(istream& is, vector<T> &v) { for(auto &x : v) is >> x; return is; }
void in(){} template <typename T,class... U> void in(T &t,U &...u){ cin >> t; in(u...);}
void out(){cout << "\n";} template <typename T,class... U> void out(const T &t,const U &...u){ cout << t; if(sizeof...(u)) cout << " "; out(u...);}
template<typename T>void die(T x){out(x); exit(0);}
#ifdef NyaanDebug
  #include "NyaanDebug.h"
  #define trc(...) do { cerr << #__VA_ARGS__ << " = "; dbg_out(__VA_ARGS__);} while(0)
  #define trca(v,...) do { cerr << #v << " = "; array_out(v , __VA_ARGS__ );} while(0)
#else
  #define trc(...)
  #define trca(...)
  int main(){solve();}
#endif
 
using P = pair<int,int>;
using vp = vector<P>;
constexpr int MOD = /**/ 1000000007; //*/ 998244353;
/////////////////

// セグ木
template<typename T,typename F>
struct ST{

  int size;
  vector<T> seg;
  const F func;
  const T UNIT;
  
  ST(int N,F func , T UNIT): func(func) , UNIT(UNIT) {
    size = 1;
    while(size < N) size <<= 1;
    seg.assign(2 * size, UNIT);
  }

  ST(const vector<T> &v,F func , T UNIT) : func(func) , UNIT(UNIT){
    // initialize
    int N = (int)v.size();
    size = 1;
    while(size < N) size <<= 1;
    seg.assign(2 * size , UNIT);
    // set
    for(int i = 0; i < N; i++){
      seg[i + size] = v[i];
    }
    build();
  }

  void set(int k, T x){
    seg[k + size] = x;
  }

  void build(){
    for(int k = size-1; k > 0; k--){
      seg[k] = func(seg[2 * k] , seg[2 * k + 1] );
    }
  }
  
  void update(int k, T x){
    k += size; seg[k] = x;
    while(k >>= 1){
      seg[k] = func( seg[2 * k] , seg[2 * k + 1] );
    }
  }

  void add(int k , T x){
    k += size; seg[k] += x;
    while(k >>= 1){
      seg[k] = func(seg[2 * k] , seg[2 * k + 1] );
    }
  }
  
  // 半開区間[a,b)へのクエリ
  T query(int a, int b){
    T L = UNIT, R = UNIT;
    for(a+=size,b+=size; a<b; a>>=1,b>>=1){
      if(a & 1) L = func(L,seg[a++]);
      if(b & 1) R = func(seg[--b],R);
    }
    return func(L, R);
  }

  T operator[](const int &k) const{
    return seg[k + size];
  }

};

// 遅延伝播セグメント木
template <typename T,typename E,typename F,typename G,typename H>
struct LST{
  int n,height;
  F f;
  G g;
  H h;
  T ti;
  E ei;
  vector<T> dat;
  vector<E> laz;
  LST(int n, F f,G g,H h,T ti,E ei):
    f(f),g(g),h(h),ti(ti),ei(ei){
      init(n);
  }
  LST(const vector<T> &v, F f,G g,H h,T ti,E ei):
    f(f),g(g),h(h),ti(ti),ei(ei){
      init( (int)v.size() );
      build(v);
  }
  
  void init(int n_){
    n=1;height=0;
    while(n<n_) n<<=1,height++;
    dat.assign(2*n,ti);
    laz.assign(2*n,ei);
  }
  void build(const vector<T> &v){
    int n_=v.size();
    init(n_);
    for(int i=0;i<n_;i++) dat[n+i]=v[i];
    for(int i=n-1;i;i--)
      dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
  }
  inline T reflect(int k){
    return laz[k]==ei?dat[k]:g(dat[k],laz[k]);
  }
  inline void eval(int k){
    if(laz[k]==ei) return;
    laz[(k<<1)|0]=h(laz[(k<<1)|0],laz[k]);
    laz[(k<<1)|1]=h(laz[(k<<1)|1],laz[k]);
    dat[k]=reflect(k);
    laz[k]=ei;
  }
  inline void thrust(int k){
    for(int i=height;i;i--) eval(k>>i);
  }
  inline void recalc(int k){    
    while(k>>=1)
      dat[k]=f(reflect((k<<1)|0),reflect((k<<1)|1));
  }
  void update(int a,int b,E x){
    thrust(a+=n);
    thrust(b+=n-1);
    for(int l=a,r=b+1;l<r;l>>=1,r>>=1){
      if(l&1) laz[l]=h(laz[l],x),l++;
      if(r&1) --r,laz[r]=h(laz[r],x);
    }
    recalc(a);
    recalc(b);
  }
  void set_val(int a,T x){
    thrust(a+=n);
    dat[a]=x;laz[a]=ei;
    recalc(a);
  }
  T query(int a,int b){
    thrust(a+=n);
    thrust(b+=n-1);
    T vl=ti,vr=ti;
    for(int l=a,r=b+1;l<r;l>>=1,r>>=1) {
      if(l&1) vl=f(vl,reflect(l++));
      if(r&1) vr=f(reflect(--r),vr);
    }
    return f(vl,vr);
  }
};

// BIT

template< typename T >
struct BIT {
  int N; int max_2beki;

  vector< T > data;
  // 初期化 1-indexedでデータを管理する 0で初期化
  BIT(int size){
      N = ++size;
      data.assign(N, 0);
      max_2beki = 1;
      while(max_2beki * 2 <= N) max_2beki *= 2;
  }

  // [0,k](閉区間)の総和 閉区間に注意！
  T sum(int k) {
    if(k < 0) return 0; // k<0のとき0を返す
    T ret = 0;
    for(++k; k > 0; k -= k & -k) ret += data[k];
    return (ret);
  }

  // [l,r](閉区間)の総和
  inline T sum(int l,int r){
    return sum(r) - sum(l-1);
  }

  // 一点取得 更新はできないことに注意
  inline T operator[](int k){
    return sum(k) - sum(k-1);
  }

  // data[k] += x;
  void add(int k, T x) {
    for(++k; k < N; k += k & -k) data[k] += x;
  }

  // imos法 [l,r]にxを加算
  void imos(int l,int r,T x){
    add(l , x); add(r + 1 , -x);
  }

  // lower_bound sum(i)がval以上となる最小のi
  int lower_bound(T w){
    if(w <= 0) return 0;
    int x = 0;
    for(int k = max_2beki; k > 0; k /= 2){
      if(x+k <= N - 1 && data[x + k] < w){
        w -= data[x + k];
        x += k;
      }
    }
    return x;
  }

  // upper_bound sum(i)がvalより大きくなる最小のi
  int upper_bound(T w){
    if(w < 0) return 0;
    int x = 0;
    for(int k = max_2beki; k > 0; k /= 2){
      if(x+k <= N - 1 && data[x + k] <= w){
        w -= data[x + k];
        x += k;
      }
    }
    return x;
  }

};


template<typename T>
struct BIT2D{
  int H,W;
  vector<vector<T>> bit;
  BIT2D(int H,int W):H(H),W(W){
    bit.resize(H + 1 , vector<T>(W + 1 , 0));
  }
  // 関数の入力のindexは0-originを想定

  // (x,y)にwを足す
  // 範囲外の時は足さない
  void add(int x, int y, T w){
    if(x < 0 || x >= H || y < 0 || y >= W) return;
    for(int a = (++y , ++x); a <= H; a += a & -a){
      for(int b = y ; b <= W; b += b & -b){
        bit[a][b] += w;
      }
    }
  }

  // imos法で[(x1,y1) , (x2,y2)]にwを足す
  void imos(int x1, int y1, int x2, int y2, T w){
    add(x1 , y1 , w);
    add(x1 , y2 + 1 , -w);
    add(x2 + 1 , y1 , -w);
    add(x2 + 1 , y2 + 1 , w);
  }

  //  [(0,0) , (x,y)]の和　閉区間に注意！
  // x,y<0の時は0 x>=H y>=Wのときはx=H-1,y=W-1とみなす
  // ( imos法の時は (x,y)の値を返す )
  T sum(int x, int y){
    if(x < 0 || y < 0) return 0;
    if(x >= H) return 0;
    if(y >= W) return 0;
    T ret = 0;
    for(int a = (++y , ++x) ; a > 0; a -= a & -a){
      for(int b = y; b > 0; b -= b & -b){
        ret += bit[a][b];
      }
    }
    return ret;
  }

  // [(x1,y1) , (x2,y2)] の和
  // x1 > x2, y1 > y2の時はswap
  T sum(int x1,int y1, int x2, int y2){
    if(x1 > x2) swap(x1 , x2);
    if(y1 > y2) swap(y1 , y2);
    return sum(x2,y2)-sum(x2,y1-1)-sum(x1-1,y2)+sum(x1-1,y1-1);
  }
};

void solve(){
  /*
  using Monoid = ll;
  auto f = [](Monoid a,Monoid b){return a + b; };
  using SEG = ST<Monoid , decltype(f)>;
  */
  ini(N,Q);
  vl a(N) ; in(a);
  vi ord(N); iota(all(ord) , 0);
  sort(all(ord),[&](int l,int r){return a[l] < a[r];});
  trc(ord);
  int bitn = min(N,200);
  BIT2D<ll> bit(N , bitn) , bitexist(N,bitn);
  auto bidx = [&](int idx)->int{return int(1LL * idx * bitn / N);};
  vi l(bitn) , r(bitn) , li(bitn) , ri(bitn);
  l[0] = a[ord[0]] , r[bitn-1] = a[ord[N-1]];
  li[0] = 0 , ri[bitn-1] = N-1;
  rep(i,N-1){
    if(bidx(i) + 1 == bidx(i+1)){
      r[bidx(i)] = a[ord[i]] , l[bidx(i+1)] = a[ord[i+1]];
      ri[i] = bidx(i) , li[i+1] = bidx(i+1);
    }
  }
  trc(l,r);
  rep(i,N){
    bit.add(i , bidx(ord[i]) , a[i]);
    bitexist.add(i , bidx(ord[i]) , 1);
  }

  rep(hoge,Q){
    ini(c,ln,rn); ln--; rn--; inl(x);
    auto itr = lower_bound(all(r) , x);
    if(itr == r.end()){out(0); continue;}
    int nya = itr - r.begin();
    ll ans = 0;
    //trc(nya);
    if(nya != bitn - 1){
      ans += bit.sum(ln , nya + 1 , rn , bitn-1);
      ans -= x * bitexist.sum(ln , nya + 1 , rn , bitn-1);
    }
    // itrが示す配列内を適当に探索
    for(int idx = li[nya]; idx <= ri[nya]; idx++){
      if(a[ord[idx]] >= x) ans += a[ord[idx]] - x;
    }
    
    out(ans);


  }
}
yukicoder

結果

テストケース

ソースコード
