結果
問題 | No.877 Range ReLU Query |
ユーザー |
![]() |
提出日時 | 2019-09-06 23:14:10 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 346 ms / 2,000 ms |
コード長 | 1,892 bytes |
コンパイル時間 | 1,896 ms |
コンパイル使用メモリ | 177,208 KB |
実行使用メモリ | 14,284 KB |
最終ジャッジ日時 | 2024-11-08 10:11:39 |
合計ジャッジ時間 | 6,705 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 20 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll=long long; using P=pair<ll,ll>; struct Tree{ int n; vector<ll> vec; Tree(int _n){ n=1; while(n<_n){ n*=2; } vec.assign(n*2+10,0); } void update(int k,ll x){ k+=n; vec[k]=x; k/=2; while(k){ vec[k]=vec[k*2]+vec[k*2+1]; k/=2; } } ll sum(int l,int r){ ll ans=0; l+=n; r+=n; while(l<r){ if(l%2){ ans+=vec[l]; l++; } if(r%2){ ans+=vec[r-1]; r--; } l/=2; r/=2; } return ans; } }; struct Query{ int f; ll x; int l,r; int n; Query(int n,ll x):f(0),n(n),l(n),r(n),x(x){} Query(int n,int l,int r,ll x):n(n),f(1),l(l),r(r),x(x){} bool operator<(const Query &o){ if(x==o.x){ if(f==o.f){ if(n==o.n){ return P(l,r)>P(o.l,o.r); } return n>o.n; } return f>o.f; } return x>o.x; } }; int main(){ int n,m; cin>>n>>m; vector<Query> que; for(int i=0;i<n;i++){ ll t; cin>>t; que.push_back(Query(i,t)); } for(int i=0;i<m;i++){ int a,b,c,d; cin>>a>>b>>c>>d; b--;c--; que.push_back(Query(i,b,c,d)); } sort(que.begin(),que.end()); Tree tr(n); Tree cn(n); vector<ll> ans(m); for(int i=0;i<que.size();i++){ Query t=que[i]; if(t.f){ ans[t.n]=tr.sum(t.l,t.r+1)-cn.sum(t.l,t.r+1)*t.x; }else{ tr.update(t.n,t.x); cn.update(t.n,1); } } for(int i=0;i<m;i++){ cout<<ans[i]<<endl; } return 0; }