結果
問題 | No.1000 Point Add and Array Add |
ユーザー | kibuna |
提出日時 | 2020-02-28 21:51:29 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 460 ms / 2,000 ms |
コード長 | 3,928 bytes |
コンパイル時間 | 2,555 ms |
コンパイル使用メモリ | 181,388 KB |
実行使用メモリ | 20,312 KB |
最終ジャッジ日時 | 2023-08-03 20:04:22 |
合計ジャッジ時間 | 8,098 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 2 ms
4,376 KB |
testcase_04 | AC | 1 ms
4,376 KB |
testcase_05 | AC | 2 ms
4,380 KB |
testcase_06 | AC | 1 ms
4,380 KB |
testcase_07 | AC | 1 ms
4,376 KB |
testcase_08 | AC | 1 ms
4,380 KB |
testcase_09 | AC | 2 ms
4,376 KB |
testcase_10 | AC | 1 ms
4,376 KB |
testcase_11 | AC | 2 ms
4,376 KB |
testcase_12 | AC | 3 ms
4,380 KB |
testcase_13 | AC | 2 ms
4,376 KB |
testcase_14 | AC | 4 ms
4,376 KB |
testcase_15 | AC | 4 ms
4,376 KB |
testcase_16 | AC | 310 ms
19,120 KB |
testcase_17 | AC | 262 ms
12,064 KB |
testcase_18 | AC | 455 ms
20,296 KB |
testcase_19 | AC | 459 ms
20,312 KB |
testcase_20 | AC | 236 ms
20,204 KB |
testcase_21 | AC | 459 ms
20,260 KB |
testcase_22 | AC | 378 ms
20,284 KB |
testcase_23 | AC | 460 ms
20,288 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using lint = long long; const lint inf = 1LL << 60; const lint mod = 1000000007; template <typename T = lint> struct SegmentTreeLazyAdd { private: using F = function<T(T, T)>; using G = function<int(int, int)>; int n; vector<T> node, lazy, width; vector<bool> lazyFlag; F func; G funcw; T unit; public: SegmentTreeLazyAdd(int sz, F func, G funcw, T unit) : func(func), funcw(funcw), unit(unit) { n = 1; while (n < sz) n *= 2; node.assign(2 * n - 1, unit); lazy.assign(2 * n - 1, 0); lazyFlag.assign(2 * n - 1, false); width.assign(2 * n - 1, 1); for (int i = n - 2; i >= 0; --i) { width[i] = funcw(width[i * 2 + 1], width[i * 2 + 2]); } } SegmentTreeLazyAdd(vector<T> v, F func, G funcw, T unit) : func(func), funcw(funcw), unit(unit) { int sz = int(v.size()); n = 1; while (n < sz) n *= 2; node.assign(2 * n - 1, unit); lazy.assign(2 * n - 1, 0); lazyFlag.assign(2 * n - 1, false); for (int i = 0; i < sz; i++) node[i + n - 1] = v[i]; for (int i = n - 2; i >= 0; i--) node[i] = func(node[i * 2 + 1], node[i * 2 + 2]); width.assign(2 * n - 1, 1); for (int i = n - 2; i >= 0; --i) { width[i] = funcw(width[i * 2 + 1], width[i * 2 + 2]); } } void lazyEvaluate(int k, int l, int r) { if (lazyFlag[k]) { node[k] += lazy[k] * width[k]; if (r - l > 1) { lazy[k * 2 + 1] += lazy[k]; lazy[k * 2 + 2] += lazy[k]; lazyFlag[k * 2 + 1] = lazyFlag[k * 2 + 2] = true; } lazyFlag[k] = false; lazy[k] = 0; } } // add x to nodes in [a, b) void add(int a, int b, T x, int k = 0, int l = 0, int r = -1) { if (r < 0) r = n; lazyEvaluate(k, l, r); if (b <= l || r <= a) { return; } if (a <= l && r <= b) { lazy[k] += x; // += lazyFlag[k] = true; lazyEvaluate(k, l, r); return; } else { const int mid = (l + r) / 2; add(a, b, x, k * 2 + 1, l, mid); add(a, b, x, k * 2 + 2, mid, r); node[k] = func(node[2 * k + 1], node[2 * k + 2]); } } // get func() in [a, b) T query(int a, int b, int k = 0, int l = 0, int r = -1) { if (r < 0) r = n; lazyEvaluate(k, l, r); if (b <= l || r <= a) return unit; if (a <= l && r <= b) return node[k]; T vl = query(a, b, 2 * k + 1, l, (l + r) / 2); T vr = query(a, b, 2 * k + 2, (l + r) / 2, r); return func(vl, vr); } }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int n, q; cin >> n >> q; vector<lint> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } vector<char> c(q); vector<int> x(q), y(q); for (int i = 0; i < q; ++i) { cin >> c[i] >> x[i] >> y[i]; x[i]--; if (c[i] == 'B') y[i]--; } vector<lint> b(n, 0); auto f = [](lint l, lint r) { return l + r; }; auto g = [](int l, int r) { return l + r; }; SegmentTreeLazyAdd<lint> seg(n, f, g, 0); for (int i = q - 1; i >= 0; --i) { if (c[i] == 'A') { lint cnt = seg.query(x[i], x[i] + 1); b[x[i]] += cnt * y[i]; } else if (c[i] == 'B') { seg.add(x[i], y[i] + 1, 1); } } for (int i = 0; i < n; ++i) { lint cnt = seg.query(i, i + 1); b[i] += a[i] * cnt; } for (int i = 0; i < n; ++i) { if (i != 0) cout << " "; cout << b[i]; } cout << endl; return 0; }