結果

問題 No.1000 Point Add and Array Add
ユーザー MayimgMayimg
提出日時 2020-02-28 21:43:10
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 231 ms / 2,000 ms
コード長 3,752 bytes
コンパイル時間 2,488 ms
コンパイル使用メモリ 209,840 KB
実行使用メモリ 29,684 KB
最終ジャッジ日時 2024-04-21 18:13:03
合計ジャッジ時間 6,220 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 3 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 4 ms
5,376 KB
testcase_15 AC 3 ms
5,376 KB
testcase_16 AC 160 ms
22,140 KB
testcase_17 AC 141 ms
18,248 KB
testcase_18 AC 231 ms
27,764 KB
testcase_19 AC 225 ms
27,764 KB
testcase_20 AC 200 ms
29,684 KB
testcase_21 AC 216 ms
25,460 KB
testcase_22 AC 223 ms
29,304 KB
testcase_23 AC 224 ms
25,968 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
template <typename Monoid, typename LazyMonoid, typename FunctionMonoid, typename FunctionAction, typename FunctionLazy> class LazySegmentTree {
private:
  //using FunctionMonoid = function<Monoid(Monoid, Monoid)>;
  //using FunctionAction = function<Monoid(Monoid, LazyMonoid)>;
  //using FunctionLazy = function<LazyMonoid(LazyMonoid, LazyMonoid)>;
  FunctionMonoid fm;
  FunctionAction fa;
  FunctionLazy fl;
  int n, height;
  vector<Monoid> data;
  vector<LazyMonoid> lazy;
  Monoid M_UNITY;
  LazyMonoid L_UNITY;
  void build (const int siz) {
    n = 1;
    height = 0;
    while (n < siz) n <<= 1, ++height;
    data.assign(2 * n, M_UNITY);
    lazy.assign(2 * n, L_UNITY);
  }
public:
  LazySegmentTree (const FunctionMonoid& f, const FunctionAction& g, const FunctionLazy& h, const Monoid& m_unity, const LazyMonoid& l_unity, int siz = 1) 
  : fm(f), fa(g), fl(h), M_UNITY(m_unity), L_UNITY(l_unity) {
    build(siz);
  }
  inline Monoid reflect (int k) {
    return lazy[k] == L_UNITY ? data[k] : fa(data[k], lazy[k]);
  }
  inline void propagate (int k) {
    if (lazy[k] == L_UNITY) return;
    lazy[(k << 1) | 0] = fl(lazy[(k << 1) | 0], lazy[k]);
    lazy[(k << 1) | 1] = fl(lazy[(k << 1) | 1], lazy[k]);
    data[k] = reflect(k);
    lazy[k] = L_UNITY;
  }
  inline void thrust (int k) {
    for (int i = height; i > 0; --i) propagate(k >> i);
  }
  inline void recalc (int k) {
    while (k >>= 1) data[k] = fm(reflect((k << 1) | 0), reflect((k << 1) | 1));
  }
  void modify (int left, int right, LazyMonoid val) {
    thrust(left += n);
    thrust(right += n - 1);
    for (int l = left, r = right + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1) lazy[l] = fl(lazy[l], val), l++;
      if (r & 1) --r, lazy[r] = fl(lazy[r], val);
    }
    recalc(left);
    recalc(right);
  }
  void modify (int idx, LazyMonoid val) {
    thrust(idx += n);
    data[idx] = val;
    lazy[idx] = L_UNITY;
    recalc(idx);
  }
  Monoid get (int left, int right) {
    thrust(left += n);
    thrust(right += n - 1);
    Monoid val_l = M_UNITY, val_r = M_UNITY;
    for (int l = left, r = right + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1) val_l = fm(val_l, reflect(l++));
      if (r & 1) val_r = fm(reflect(--r), val_r);
    }
    return fm(val_l, val_r);
  }
};
signed main() { 
  ios::sync_with_stdio(false); cin.tie(0);
  //c
  int n, q;
  cin >> n >> q;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  vector<vector<int>> query;
  for (int i = 0; i < q; i++) {
    char ch;
    cin >> ch;
    int c = (ch == 'A');
    int x, y;
    cin >> x >> y;
    if (c == 1) x--;
    else x--, y--;
    query.push_back({c, x, y});
  }
  reverse(query.begin(), query.end());
  auto f = [] (int x, int y) { return x + y; };
  LazySegmentTree<int, int, decltype(f), decltype(f), decltype(f)> sgt (f, f, f, 0, 0, n + 10);
  for (int i = 0; i < n; i++) sgt.modify(i, 0);
  vector<vector<pair<int, int>>> add(n);
  for (int i = 0; i < q; i++) {
    if (query[i][0] == 0) {
      int l = query[i][1];
      int r = query[i][2];
      sgt.modify(l, r + 1, 1);
      //cerr << l << " " << r << endl;
    } else {
      int idx = query[i][1];
      int val = query[i][2];
      add[idx].emplace_back(val, sgt.get(idx, idx + 1));
    }
  }
  // for (int i = 0; i < n; i++) {
  //   cerr << sgt.get(i, i + 1) << " ";
  // }
  // cerr << endl;
  vector<long long> ans(n);
  for (int i = 0; i < n; i++) {
    for (auto& p : add[i]) {
      ans[i] += 1LL * p.first * p.second;
    }
  }
  for (int i = 0; i < n; i++) {
    ans[i] += 1LL * a[i] * sgt.get(i, i + 1);
  }
  for (int i = 0; i < n; i++) {
    if (i > 0) cout << " ";
    cout << ans[i];
  }
  cout << endl;
  return 0;
}
0