結果

問題 No.1000 Point Add and Array Add
コンテスト
ユーザー どらら
提出日時 2020-02-28 22:32:03
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 576 ms / 2,000 ms
コード長 4,075 bytes
コンパイル時間 2,181 ms
コンパイル使用メモリ 187,232 KB
実行使用メモリ 26,176 KB
最終ジャッジ日時 2024-10-13 18:20:38
合計ジャッジ時間 8,178 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

template <class Monoid, class OpMonoid>
class LazySegmentTree {
  using FuncMM = std::function<Monoid(Monoid, Monoid)>;
  using FuncMO = std::function<Monoid(Monoid, OpMonoid, int)>;
  using FuncOO = std::function<OpMonoid(OpMonoid, OpMonoid)>;

  const FuncMM funcMM;
  const FuncMO funcMO;
  const FuncOO funcOO;
  const Monoid monoidIdentity;
  const OpMonoid opMonoidIdentity;

  int N;
  std::vector<Monoid> dat;
  std::vector<OpMonoid> lazy;

  void setLazy(int k, const OpMonoid& om) { lazy[k] = funcOO(lazy[k], om); }
  void push(int k, int len) {
    if (lazy[k] == opMonoidIdentity) return;
    if (k < N) {
      setLazy(2 * k + 0, lazy[k]);
      setLazy(2 * k + 1, lazy[k]);
    }
    dat[k] = funcMO(dat[k], lazy[k], len);
    lazy[k] = opMonoidIdentity;
  }

 public:
  LazySegmentTree(int n, const FuncMM funcMM, const FuncMO funcMO,
                  const FuncOO funcOO, const Monoid monoidIdentity,
                  const OpMonoid opMonoidIdentity)
      : funcMM(funcMM),
        funcMO(funcMO),
        funcOO(funcOO),
        monoidIdentity(monoidIdentity),
        opMonoidIdentity(opMonoidIdentity) {
    N = 1;
    while (N < n) N *= 2;
    dat.resize(2 * N, monoidIdentity);
    lazy.resize(2 * N, opMonoidIdentity);
  }

  void dump() {
    std::cout << "dat: ";
    for (int i = 1; i < dat.size(); i++) {
      if (i == N) std::cout << "| ";
      std::cout << dat[i].ai << "(" << lazy[i].p << "," << lazy[i].q << ","
                << lazy[i].r << ") ";
    }
    std::cout << std::endl;
  }

  void set(int i, const Monoid& v) { dat[N + i] = v; }

  void init() {
    for (int i = N - 1; i > 0; i--) {
      dat[i] = funcMM(dat[2 * i + 0], dat[2 * i + 1]);
    }
  }

  void update(int s, int t, const OpMonoid& om) { update(s, t, om, 1, 0, N); }
  void update(int s, int t, const OpMonoid& om, int k, int l, int r) {
    push(k, r - l);
    if (r <= s || t <= l) return;
    if (s <= l && r <= t) {
      setLazy(k, om);
      push(k, r - l);
      return;
    }
    update(s, t, om, 2 * k + 0, l, (l + r) / 2);
    update(s, t, om, 2 * k + 1, (l + r) / 2, r);
    dat[k] = funcMM(dat[2 * k + 0], dat[2 * k + 1]);
  }

  Monoid query(int s, int t) { return query(s, t, 1, 0, N); }
  Monoid query(int s, int t, int k, int l, int r) {
    push(k, r - l);
    if (r <= s || t <= l) return monoidIdentity;
    if (s <= l && r <= t) return dat[k];
    Monoid vl = query(s, t, 2 * k + 0, l, (l + r) / 2);
    Monoid vr = query(s, t, 2 * k + 1, (l + r) / 2, r);
    return funcMM(vl, vr);
  }
};

struct VAL {
  ll ai;
};

struct OP {
  ll p;
};
bool operator==(const OP& a, const OP& b) {
  return a.p == b.p;
}


int main(){
  int N, Q;
  cin >> N >> Q;
  vector<ll> v;
  rep(i,N){
    ll a;
    cin >> a;
    v.push_back(a);
  }
  vector<vector<ll>> w;
  rep(i,Q){
    char c;
    ll x, y;
    cin >> c >> x >> y;
    ll t = (c=='A')?0:1;
    w.push_back({t,x,y});
  }
  reverse(ALLOF(w));
  
  auto funcMM = [](const VAL& a, const VAL& b) {
    VAL ret;
    ret.ai = a.ai + b.ai;
    return ret;
  };
  auto funcMO = [](const VAL& a, const OP& b, int k) {
    VAL ret;
    ret.ai = (a.ai + b.p) * k;
    return ret;
  };
  auto funcOO = [](const OP& a, const OP& b) {
    OP ret;
    ret.p = b.p + a.p;
    return ret;
  };

  LazySegmentTree<VAL, OP> lst(N, funcMM, funcMO, funcOO, (VAL){0},
                               (OP){0});

  vector<ll> ret(N, 0);

  rep(i,Q){
    if(w[i][0] == 0){
      int ii = w[i][1]-1;
      ll val = w[i][2];
      ll cnt = lst.query(ii,ii+1).ai;
      ret[ii] += val * cnt;
    }else{
      lst.update(w[i][1]-1, w[i][2], (OP){1});
    }
  }

  rep(i,ret.size()){
    if(i>0) cout << " ";
    ll cnt = lst.query(i,i+1).ai;
    ll sum = ret[i] + v[i] * cnt;
    cout << sum;
  }
  cout << endl;
  return 0;
}
0