結果
問題 |
No.3078 Difference Sum Query
|
ユーザー |
![]() |
提出日時 | 2025-03-28 21:48:09 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,627 ms / 2,000 ms |
コード長 | 1,074 bytes |
コンパイル時間 | 4,113 ms |
コンパイル使用メモリ | 256,192 KB |
実行使用メモリ | 7,324 KB |
最終ジャッジ日時 | 2025-03-28 21:48:42 |
合計ジャッジ時間 | 22,533 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 26 |
ソースコード
#include <stdio.h> #include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000000 #define Inf64 1000000000000000001LL int main(){ int n,q; cin>>n>>q; vector<long long> a(n); rep(i,n)cin>>a[i]; int B = 500; vector<vector<long long>> as((n+B-1)/B); rep(i,n)as[i/B].push_back(a[i]); vector<vector<long long>> sums(as.size()); rep(i,as.size()){ sort(as[i].begin(),as[i].end()); sums[i].resize(as[i].size()+1); rep(j,as[i].size())sums[i][j+1]=sums[i][j]+as[i][j]; } rep(_,q){ int L,R; long long X; cin>>L>>R>>X; L--; long long ans = 0; while(L%B != 0 && L<R){ ans += abs(a[L] - X); L++; } while(L+B <= R){ int ii = L / B; int d = distance(as[ii].begin(),lower_bound(as[ii].begin(),as[ii].end(),X)); ans += X * d - sums[ii][d]; ans += sums[ii].back()-sums[ii][d] - X * (as[ii].size()-d); L += B; } while(L<R){ ans += abs(a[L] - X); L++; } cout<<ans<<endl; } return 0; }