結果
問題 | No.877 Range ReLU Query |
ユーザー |
![]() |
提出日時 | 2019-09-06 22:22:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 313 ms / 2,000 ms |
コード長 | 1,208 bytes |
コンパイル時間 | 1,067 ms |
コンパイル使用メモリ | 82,692 KB |
最終ジャッジ日時 | 2025-01-07 16:52:58 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 20 |
ソースコード
#include <iostream> #include <algorithm> #include <vector> #include <utility> using namespace std; using ll = long long; ll n,mx = 100000000000000; pair<ll,ll> t[200010]; pair<ll,ll> add(pair<ll,ll> p, pair<ll,ll> q){ p.first += q.first; p.second += q.second; return p; } void update(ll p,ll a){ for(t[p += n] = {a,1};p>1;p >>= 1){ t[p>>1] = add(t[p],t[p^1]); } } pair<ll,ll> query(ll l, ll r){ pair<ll,ll> mn = {0LL,0LL}; for(l += n, r += n; l<r; l >>= 1,r >>= 1){ if(l&1) mn = add(mn,t[l++]); if(r&1) mn = add(mn,t[--r]); } return mn; } pair<ll,ll> p[100010]; pair<ll,pair<ll,pair<ll,ll>>> qu[100010]; ll ans[100010]; int main(){ int i,q; cin >> n >> q; for(i=0;i<n;i++){ ll x; cin >> x; p[i] = {x,i}; } for(i=0;i<q;i++){ ll b,x,l,r; cin >> b >> l >> r >> x; l--; qu[i] = {x,{i,{l,r}}}; } sort(p,p + n); sort(qu,qu + q); int j = n - 1; for(i=q - 1;i>=0;i--){ ll val = qu[i].first,ind = qu[i].second.first,l = qu[i].second.second.first,r = qu[i].second.second.second; while(j>=0 && p[j].first>val){ update(p[j].second,p[j].first); j--; } pair<ll,ll> z = query(l,r); ans[ind] = z.first - z.second*val; } for(i=0;i<q;i++){ cout << ans[i] << endl; } }