#435956 (C++14) No.1000 Point Add and Array Add

• 問題: No.1000 Point Add and Array Add
• ユーザー: startcpp
• 提出日時: 2020-02-28 21:44:50
• 言語: C++14 (gcc 13.2.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 366 ms / 2,000 ms
• コード長: 1,233 bytes
• コンパイル時間: 629 ms
• コンパイル使用メモリ: 67,700 KB
• 実行使用メモリ: 14,080 KB
• 最終ジャッジ日時: 2024-04-21 18:14:23
• 合計ジャッジ時間: 5,001 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	4 ms; 7,680 KB
testcase_01	AC	4 ms; 7,552 KB
testcase_02	AC	4 ms; 7,808 KB
testcase_03	AC	4 ms; 7,808 KB
testcase_04	AC	4 ms; 7,680 KB
testcase_05	AC	4 ms; 7,808 KB
testcase_06	AC	4 ms; 7,680 KB
testcase_07	AC	4 ms; 7,680 KB
testcase_08	AC	4 ms; 7,680 KB
testcase_09	AC	4 ms; 7,808 KB
testcase_10	AC	5 ms; 7,680 KB
testcase_11	AC	3 ms; 7,680 KB
testcase_12	AC	7 ms; 7,680 KB
testcase_13	AC	5 ms; 7,936 KB
testcase_14	AC	7 ms; 7,680 KB
testcase_15	AC	6 ms; 7,936 KB
testcase_16	AC	237 ms; 12,672 KB
testcase_17	AC	204 ms; 11,520 KB
testcase_18	AC	332 ms; 13,952 KB
testcase_19	AC	331 ms; 13,952 KB
testcase_20	AC	240 ms; 13,988 KB
testcase_21	AC	366 ms; 14,080 KB
testcase_22	AC	267 ms; 13,952 KB
testcase_23	AC	357 ms; 14,080 KB

ソースコード

#include <iostream>
#define int long long
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;

//区間加算、1点クエリ
const int DEPTH = 18;
struct SegTree {
	int val[1 << (DEPTH + 1)];
	SegTree() {
		int i;
		rep(i, (1 << (DEPTH + 1))) val[i] = 0;
	}
	void add(int l, int r, int x, int a = 0, int b = (1 << DEPTH), int id = 0) {
		if (a >= r || b <= l) return;
		if (l <= a && b <= r) { val[id] += x; return; }
		add(l, r, x, a, (a + b) / 2, id * 2 + 1);
		add(l, r, x, (a + b) / 2, b, id * 2 + 2);
	}
	int get(int pos) {
		pos += (1 << DEPTH) - 1;
		int ret = val[pos];
		while (pos > 0) {
			pos = (pos - 1) / 2;
			ret += val[pos];
		}
		return ret;
	}
};

int n, q;
int a[200000];
char c[200000]; int x[200000], y[200000];
SegTree seg;
int B[200000];

signed main() {
	int i;
	
	cin >> n >> q;
	rep(i, n) cin >> a[i];
	rep(i, q) {
		cin >> c[i] >> x[i] >> y[i];
		x[i]--;
	}
	
	rep(i, q) {
		if (c[i] == 'B') {
			seg.add(x[i], y[i], 1);	//[x, y)
		}
	}
	
	rep(i, n) {
		B[i] = seg.get(i) * a[i];
	}
	
	rep(i, q) {
		if (c[i] == 'A') {
			B[x[i]] += seg.get(x[i]) * y[i];
		}
		else {
			seg.add(x[i], y[i], -1);
		}
	}
	
	rep(i, n) {
		cout << B[i];
		if (i + 1 < n) cout << " ";
	}
	cout << endl;
	return 0;
}