結果
問題 | No.1099 Range Square Sum |
ユーザー |
![]() |
提出日時 | 2020-06-26 22:39:14 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,185 bytes |
コンパイル時間 | 1,635 ms |
コンパイル使用メモリ | 172,760 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-04 22:29:15 |
合計ジャッジ時間 | 7,264 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 10 WA * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define reps(i,s,n) for(int i = s; i < n; i++) #define rep(i,n) reps(i,0,n) #define Rreps(i,n,e) for(int i = n - 1; i >= e; --i) #define Rrep(i,n) Rreps(i,n,0) #define ALL(a) a.begin(), a.end() #define fi first #define se second typedef long long ll; typedef vector<ll> vec; typedef vector<vec> mat; ll N,M,H,W,Q,K,A,B; string S; const ll MOD = 998244353; //const ll MOD = (1e+9) + 7; typedef pair<ll, ll> P; const ll INF = (1LL<<58); int main() { const int bnum = 450, bsize = 450, max_n = bnum * bsize; cin >> N; vec a(max_n, 0); rep(i,N) cin>>a[i]; vec as(bnum, 0), as2(bnum, 0), tx(bnum, 0); rep(i,N){ as[i / bsize] += a[i]; as2[i / bsize] += a[i] * a[i]; } cin>>Q; rep(_,Q){ int q, l, r, x; cin>>q>>l>>r; --l; --r; int lb = l / bsize, rb = r / bsize; if(q == 1){ cin>>x; if(lb < rb) { reps(i, lb * bsize, (lb + 1) * bsize) { int temp = (i >= l ? x : 0); as2[lb] += (a[i] + tx[lb] + temp) * (a[i] + tx[lb] + temp) - a[i] * a[i]; as[lb] += tx[lb] + temp; a[i] += tx[lb] + temp; } reps(i, rb * bsize, (rb + 1) * bsize) { int temp = (i <= r ? x : 0); as2[rb] += (a[i] + tx[rb] + temp) * (a[i] + tx[rb] + temp) - a[i] * a[i]; as[rb] += tx[rb] + temp; a[i] += tx[rb] + temp; } tx[lb] = tx[rb] = 0; reps(i, lb + 1, rb) tx[i] += x; }else{ reps(i, lb * bsize, (lb + 1) * bsize) { int temp = (i >= l && i <= r ? x : 0); as2[lb] += (a[i] + tx[lb] + temp) * (a[i] + tx[lb] + temp) - a[i] * a[i]; as[lb] += tx[lb] + temp; a[i] += tx[lb] + temp; } tx[lb] = 0; } }else{ ll res = 0; if(lb < rb) { as[lb] += tx[lb] * bsize; as[rb] += tx[rb] * bsize; reps(i, lb * bsize, (lb + 1) * bsize) { as2[lb] += (a[i] + tx[lb]) * (a[i] + tx[lb]) - a[i] * a[i]; a[i] += tx[lb]; if (i >= l) res += a[i] * a[i]; } reps(i, rb * bsize, (rb + 1) * bsize) { as2[rb] += (a[i] + tx[rb]) * (a[i] + tx[rb]) - a[i] * a[i]; a[i] += tx[rb]; if (i <= r) res += a[i] * a[i]; } tx[lb] = tx[rb] = 0; reps(i, lb + 1, rb) res += as2[i] + 2LL * as[i] * tx[i] + tx[i] * tx[i]; }else{ as[lb] += tx[lb] * bsize; reps(i, lb * bsize, (lb + 1) * bsize) { as2[lb] += (a[i] + tx[lb]) * (a[i] + tx[lb]) - a[i] * a[i]; a[i] += tx[lb]; if(i >= l && i <= r) res += a[i] * a[i]; } tx[lb] = 0; } cout<<res<<endl; } } }