結果
問題 | No.877 Range ReLU Query |
ユーザー |
![]() |
提出日時 | 2019-09-06 22:09:04 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 430 ms / 2,000 ms |
コード長 | 2,002 bytes |
コンパイル時間 | 2,103 ms |
コンパイル使用メモリ | 181,576 KB |
実行使用メモリ | 22,996 KB |
最終ジャッジ日時 | 2024-11-08 10:03:59 |
合計ジャッジ時間 | 7,399 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define modulo 1000000007 #define mod(mod_x) ((((long long)mod_x+modulo))%modulo) #define Inf 1000000000000000 template <typename T> struct segtree{ //元データx[i]はv[n+i] //v[i]の親はv[i/2],子はv[i*2]とv[i*2+1] vector<T> v; int n; const T init_value = 0; segtree(vector<T> &x){ n=1; while(true){ if(n>=x.size())break; n*=2; } v.resize(2*n,init_value); for(int i=0;i<x.size();i++){ v[n+i]=x[i]; } for(int i=n-1;i>=0;i--){ v[i]=func(v[i*2],v[i*2+1]); } } void update(int x,T val){ x+=n; v[x]=val; while(true){ x=(x)/2; v[x]=func(v[x*2],v[x*2+1]); if(x<=0)break; } } //区間[l,r)におけるクエリ処理 T query(int l,int r){ T res = init_value; l+=n;r+=n; while(true){ if(l%2==1){ res=func(v[l],res); l++; } if(r%2==1){ res=func(v[r-1],res); r--; } if(l>=r)break; l/=2;r/=2; } return res; } T func(T a,T b){ return a+b; } void show(){ int n = 1; for(int i=1;i<v.size();i++){ for(int j=0;j<n;j++){ if(j!=0)cout<<' '; cout<<v[i+j]; } cout<<endl; i+=n-1; n*=2; } } }; int main(){ int N,Q; cin>>N>>Q; vector<vector<long long>> X; for(int i=0;i<N;i++){ long long A; cin>>A; vector<long long> x = {A,Inf,Inf,i}; X.push_back(x); } for(int i=0;i<Q;i++){ long long l,r,x; cin>>l; cin>>l>>r>>x; l--;r--; vector<long long> a = {x,l,r,i}; X.push_back(a); } sort(X.begin(),X.end(),greater<vector<long long>>()); vector<long long> fir(N,0); segtree<long long> seg1(fir),seg2(fir); vector<long long> ans(Q); for(int i=0;i<X.size();i++){ if(X[i][1]==Inf){ int ind = X[i][3]; seg1.update(ind,X[i][0]); seg2.update(ind,1); } else{ long long a = seg1.query(X[i][1],X[i][2]+1); long long b = seg2.query(X[i][1],X[i][2]+1); a -= X[i][0]*b; ans[X[i][3]]=a; } } for(int i=0;i<Q;i++){ cout<<ans[i]<<endl; } return 0; }