結果

問題 No.877 Range ReLU Query
コンテスト
ユーザー yamake
提出日時 2021-02-24 18:08:47
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 257 ms / 2,000 ms
コード長 2,090 bytes
記録
コンパイル時間 2,224 ms
コンパイル使用メモリ 182,940 KB
実行使用メモリ 10,368 KB
最終ジャッジ日時 2024-11-08 10:35:39
合計ジャッジ時間 6,162 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define debug(output) cout<<#output<<"= "<<output<<endl
using lint = long long;
typedef pair<int,int> P;
const lint linf=1e18+7;
const lint inf=1e9+7;
const int MOD=1000000007;
template<class T>
class SegTree{
    int n;
    vector<T> node;
    T e;
    function<T(T,T)> operation;
    function<T(T,T)> update;
    public:
    SegTree(int _n,T _e,function<T(T,T)> _operation,function<T(T,T)> _update):n(_n),e(_e),operation(_operation),update(_update){node.resize(n*2,e);}
    void change(int i,T x){
        i+=n;
        node[i]=update(node[i],x);
        while(i>1){
            i>>=1;
            node[i]=operation(node[i<<1|0],node[i<<1|1]);
        }
    }
    T get(int l,int r){
        T a=e;
        T b=e;
        l+=n;r+=n;
        while(l<r){
            if(l&1)a=operation(a,node[l++]);
            if(r&1)b=operation(node[--r],b);
            l>>=1;r>>=1;
        }
        return operation(a,b);
    }
    void input(vector<T>& _input){
        for(int i=0;i<n;++i){
            change(i,_input[i]);
        }
    }
};
signed main(){
  int n,q;cin>>n>>q;
  vector<lint> a(n);
  rep(i,n)cin>>a[i];
  auto op=[](lint a,lint b){return a+b;};
  auto ch=[](lint a,lint b){return b;};
  SegTree<lint> tree(n,0,op,ch);
  auto cnt=tree;
  rep(i,n)cnt.change(i,1);
  tree.input(a);
  vector<P> in(q),b(n);
  vector<int> l(q),r(q);
  rep(i,q){
      int hoge;
      cin>>hoge>>l[i]>>r[i]>>in[i].first;
      in[i].second=i;
  }
  rep(i,n)b[i]={a[i],i};
  sort(b.begin(),b.end());
  sort(in.begin(),in.end());
  int cur=0;
  auto last=b.begin();
  vector<lint> res(q,0);
  rep(i,q){
      auto it2=upper_bound(b.begin()+cur,b.end(),make_pair(in[i].first,0));
      for(auto it=last;it!=it2;++it){
          tree.change(it->second,0);
          cnt.change(it->second,0);
      }
      cur=it2-b.begin();
      last=it2;
      int x=in[i].second;
      res[x]=tree.get(l[x]-1,r[x])-cnt.get(l[x]-1,r[x])*in[i].first;
  }
  rep(i,q)cout<<res[i]<<"\n";
  return 0;
}
0