結果
問題 |
No.1000 Point Add and Array Add
|
ユーザー |
![]() |
提出日時 | 2020-02-28 21:54:04 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 346 ms / 2,000 ms |
コード長 | 1,385 bytes |
コンパイル時間 | 702 ms |
コンパイル使用メモリ | 73,728 KB |
実行使用メモリ | 13,824 KB |
最終ジャッジ日時 | 2024-10-13 17:19:58 |
合計ジャッジ時間 | 4,921 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
#include <iostream> #include <vector> using namespace std; typedef long long ll; struct seg_Lp { // 区間更新、一点取得 vector<ll> lazy; int m, n=1, n2; // initializeで初期化 void initialize(int m) { while(m > n) n<<=1; n2 = 2 * n - 1; //sum.resize(n); lazy.resize(n2); } // 増加 void add(int k, int a, int b, int v, int l, int r) { if (a <= l && r <= b) {lazy[k] += v; return;} else if (a >= r || b <= l) return; else { add(2*k+1, a, b, v, l, (l+r)/2); add(2*k+2, a, b, v, (l+r)/2, r); } } // 増加(使用用) void add(int a, int b, int v) { add(0, a, b, v, 0, n); } // 合計 int sum(int k) { k+=n-1; int ins = lazy[k]; while(k>0) { k = (k-1) / 2; ins += lazy[k]; } return ins; } }; int main(){ int n,q; cin>>n>>q; ll a[n]; for(int i=0;i<n;i++) cin>>a[i]; ll b[n]; char cc[q]; ll x[q], y[q]; for(int i=0;i<q;i++) { cin>>cc[i]>>x[i]>>y[i]; x[i]--; //y[i]--, y[i]++ } seg_Lp s; s.initialize(n); for(int i=0;i<q;i++) { if (cc[i] == 'B') s.add(x[i],y[i],1); } for(int i=0;i<n;i++) { b[i] = a[i] * s.sum(i); }/* for(int i=0;i<n;i++) { cout<<b[i]<<" "; } cout<<endl;*/ for(int i=0;i<q;i++) { if (cc[i] == 'A') b[x[i]] += s.sum(x[i]) * y[i]; else s.add(x[i],y[i],-1); } for(int i=0;i<n;i++) { cout<<b[i]<<" "; } cout<<endl; }