結果

問題 No.1000 Point Add and Array Add
コンテスト
ユーザー Strorkis
提出日時 2020-02-29 23:20:25
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 1,703 bytes
コンパイル時間 834 ms
コンパイル使用メモリ 74,032 KB
実行使用メモリ 16,084 KB
最終ジャッジ日時 2024-10-13 20:21:20
合計ジャッジ時間 6,488 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 RE * 1
other AC * 17 RE * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

struct LazySegmentTree {
  int size;
  vector<ll> node, lazy;

  LazySegmentTree(int n) {
    size = 1;
    while (size < n) size *= 2;
    node.resize(2*size-1);
    lazy.resize(2*size-1);
  }

  void eval(int k) {
    if (lazy[k] != 0) {
      node[k] += lazy[k];
      if (k <= size - 1) {
        lazy[2*k+1] += lazy[k] / 2;
        lazy[2*k+2] += lazy[k] / 2;
      }
      lazy[k] = 0;
    }
  }

  void add(int a, int b, int k=0, int l=0, int r=-1) {
    if (r < 0) r = size;
    if (b <= l || r <= a) return;
    if (a <= l && r <= b) {
      lazy[k] += r - l;
      eval(k);
    }
    else {
      eval(k);
      add(a, b, 2*k+1, l, (l+r)/2);
      add(a, b, 2*k+2, (l+r)/2, r);
      node[k] = node[2*k+1] + node[2*k+2];
    }
  }

  int get(int x, int k=0, int l=0, int r=-1) {
    if (r < 0) r = size;
    if (x < l || x >= r) return 0;
    eval(k);
    if (x + (size - 1) == k) return node[k];
    return get(x, 2*k+1, l, (l+r)/2)
         + get(x, 2*k+2, (l+r)/2, r);
  }
};

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N, Q; cin >> N >> Q;
  vector<ll> A(N);
  for (int i = 0; i < N; i++) cin >> A[i];

  LazySegmentTree st(N);
  vector<ll> B(N), check(N);
  for (int i = 0; i < Q; i++) {
    char c; cin >> c;
    int x, y; cin >> x >> y;
    if (c == 'A') {
      x--;
      int count = st.get(x);
      B[x] += A[x] * (count - check[x]);
      A[x] += y;
      check[x] = count;
    }
    else st.add(x-1, y);
  }

  for (int x = 0; x < N; x++)
    B[x] += A[x] * (st.get(x) - check[x]);

  cout << B.front();
  for (int x = 1; x < N; x++)
    cout << " " << B[x];
  cout << "\n";
}
0