結果
問題 |
No.3078 Difference Sum Query
|
ユーザー |
|
提出日時 | 2025-03-28 22:07:12 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 499 ms / 2,000 ms |
コード長 | 2,250 bytes |
コンパイル時間 | 1,883 ms |
コンパイル使用メモリ | 173,732 KB |
実行使用メモリ | 63,592 KB |
最終ジャッジ日時 | 2025-03-28 22:07:48 |
合計ジャッジ時間 | 12,068 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 26 |
コンパイルメッセージ
main.cpp: In member function ‘std::pair<int, long long int> rangefreq::query(int, int, ll, int, int, int) const’: main.cpp:50:18: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions] 50 | auto [cnt1, sum1] = query(a, b, x, k*2+1, l, (l+r)/2); | ^ main.cpp:51:18: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions] 51 | auto [cnt2, sum2] = query(a, b, x, k*2+2, (l+r)/2, r); | ^ main.cpp: In function ‘void solve()’: main.cpp:70:14: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions] 70 | auto [cnt, sum1] = freq.query(l, r+1, x); | ^
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long; using pll = pair<ll, ll>; #define all(a) (a).begin(), (a).end() #define pb push_back #define fi first #define se second mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count()); const ll MOD1000000007 = 1000000007; const ll MOD998244353 = 998244353; const ll MOD[3] = {999727999, 1070777777, 1000000007}; const ll LINF = 1LL << 60LL; const int IINF = (1 << 30) - 1; struct rangefreq{ int n; vector<vector<ll>> dat; vector<vector<ll>> sum; rangefreq(const vector<ll> &v={}){ n = 1; while(n < v.size()) n <<= 1; dat.assign(2*n-1, {}); sum.assign(2*n-1, {0}); for(int i=0;i<v.size();i++) dat[i+n-1].push_back(v[i]); for(int i=0;i<v.size();i++) sum[i+n-1].push_back(sum[i+n-1].back()+v[i]); for(int i=n-2;i>=0;i--){ dat[i].resize(dat[i*2+1].size()+dat[i*2+2].size()); merge(dat[i*2+1].begin(),dat[i*2+1].end(), dat[i*2+2].begin(),dat[i*2+2].end(), dat[i].begin() ); for(int j=0;j<dat[i].size();j++){ sum[i].push_back(sum[i].back()+dat[i][j]); } } } pair<int, ll> query(int a, int b, ll x, int k=0, int l=0, int r=-1) const //[a,b) count(*<x) { if(r<0)r=n; if(b<=l||r<=a) return {0, 0LL}; else if(a<=l&&r<=b){ int cnt = lower_bound(dat[k].begin(), dat[k].end(), x) - dat[k].begin(); return {cnt, sum[k][cnt]}; }else{ auto [cnt1, sum1] = query(a, b, x, k*2+1, l, (l+r)/2); auto [cnt2, sum2] = query(a, b, x, k*2+2, (l+r)/2, r); return {cnt1 + cnt2, sum1 + sum2}; } } }; void solve(){ int n, q; cin >> n >> q; vector<ll> a(n); for(int i=0; i<n; i++) cin >> a[i]; vector<ll> sum(n+1, 0LL); for(int i=0; i<n; i++) sum[i+1] = sum[i] + a[i]; rangefreq freq(a); while(q--){ int l, r; cin >> l >> r; l--; r--; ll x; cin >> x; int len = r - l + 1; ll s = sum[r+1] - sum[l]; auto [cnt, sum1] = freq.query(l, r+1, x); cout << (ll)cnt*x - sum1 + (s - sum1) - (ll)(len - cnt)*x << '\n'; } } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int T=1; //cin >> T; while(T--) solve(); }