結果

問題 No.1000 Point Add and Array Add
コンテスト
ユーザー sprng_wl
提出日時 2020-02-28 21:58:35
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 382 ms / 2,000 ms
コード長 2,029 bytes
コンパイル時間 1,771 ms
コンパイル使用メモリ 175,352 KB
実行使用メモリ 16,384 KB
最終ジャッジ日時 2024-10-13 17:23:02
合計ジャッジ時間 6,214 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define Int int64_t

using namespace std;

template <typename T>
struct LazySegtree {
	private:
		size_t n;
		vector<T> node, lazy;
		T M0, L0;

	public:
		LazySegtree(size_t sz, T m0, T l0) {
			n = 1;
			M0 = m0;
			L0 = l0;
			while (n < sz) { n *= 2; }
			node.assign(2*n - 1, M0);
			lazy.assign(2*n - 1, L0);
		}

		T merge(T a, T b) { return a + b; }
		void updateNode(int k, T x) { lazy[k] = lazy[k] + x; }
		void propagate(int k) { node[k] = node[k] + lazy[k]; }

		void eval(int k, int l, int r) {
			if (lazy[k] == L0) { return; }
			propagate(k);
			if (r - l > 1) {
				updateNode(2*k + 1, lazy[k]);
				updateNode(2*k + 2, lazy[k]);
			}
			lazy[k] = L0;
		}

		void update(int a, int b, T x, int k=0, int l=0, int r=-1) {
			if (r < 0) { r = n; }
			eval(k, l, r);
			if (r <= a || b <= l) { return; }
			if (a <= l && r <= b) {
				updateNode(k, x);
				eval(k, l, r);
			} else {
				update(a, b, x, 2*k + 1, l, (l + r) / 2);
				update(a, b, x, 2*k + 2, (l + r) / 2, r);
				node[k] = merge(node[2*k + 1], node[2*k + 2]);
			}
		}

		T query(int a, int b, int k=0, int l=0, int r=-1) {
			if (r < 0) { r = n; }
			eval(k, l, r);
			if (r <= a || b <= l) { return M0; }
			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 merge(vl, vr);
		}
};

int main() {
	int N, Q;
	cin >> N >> Q;
	vector<Int> 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];
	}

	LazySegtree<Int> seg(N + 1, 0, 0);
	vector<Int> b(N, 0);
	for (int i = Q - 1; i >= 0; --i) {
		if (c[i] == 'A') {
			int idx = x[i] - 1;
			Int x = seg.query(idx, idx + 1);
			b[idx] += y[i] * x;
		} else {
			seg.update(x[i] - 1, y[i], 1);
		}
	}
	for (int i = 0; i < N; ++i) {
		Int x = seg.query(i, i + 1);
		b[i] += a[i] * x;
	}

	for (int i = 0; i < N; ++i) {
		cout << b[i] << (i < N - 1 ? " " : "\n");
	}

	return 0;
}
0