結果

問題 No.1000 Point Add and Array Add
ユーザー StrorkisStrorkis
提出日時 2020-02-29 23:28:21
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 219 ms / 2,000 ms
コード長 1,702 bytes
コンパイル時間 1,186 ms
コンパイル使用メモリ 74,764 KB
実行使用メモリ 16,128 KB
最終ジャッジ日時 2024-10-13 20:21:39
合計ジャッジ時間 4,500 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 1 ms
5,248 KB
testcase_06 AC 1 ms
5,248 KB
testcase_07 AC 1 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 1 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 AC 1 ms
5,248 KB
testcase_12 AC 3 ms
5,248 KB
testcase_13 AC 2 ms
5,248 KB
testcase_14 AC 3 ms
5,248 KB
testcase_15 AC 3 ms
5,248 KB
testcase_16 AC 148 ms
15,360 KB
testcase_17 AC 123 ms
9,728 KB
testcase_18 AC 215 ms
16,128 KB
testcase_19 AC 219 ms
16,000 KB
testcase_20 AC 156 ms
16,128 KB
testcase_21 AC 216 ms
16,108 KB
testcase_22 AC 185 ms
16,128 KB
testcase_23 AC 214 ms
16,000 KB
権限があれば一括ダウンロードができます

ソースコード

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