結果

問題 No.1000 Point Add and Array Add
コンテスト
ユーザー QCFium
提出日時 2020-03-02 21:47:12
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 133 ms / 2,000 ms
コード長 1,093 bytes
コンパイル時間 1,420 ms
コンパイル使用メモリ 169,160 KB
実行使用メモリ 8,960 KB
最終ジャッジ日時 2024-10-13 21:18:20
合計ジャッジ時間 4,288 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:45:15: warning: 'void* memset(void*, int, size_t)' specified bound between 18446744073709551600 and 18446744073709551608 exceeds maximum object size 9223372036854775807 [-Wstringop-overflow=]
   45 |         memset(res, 0, sizeof(res));
      |         ~~~~~~^~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}
struct BIT {
	int n;
	std::vector<int> data;
	BIT (int n) : n(n), data(n + 1) {}
	void add(int i, int val) {
		for (i++; i <= n; i += i & -i) data[i] += val;
	}
	int sum(int i) {
		int res = 0;
		for (; i; i &= i - 1) res += data[i];
		return res;
	}
};
int main() {
	int n = ri();
	int q = ri();
	int a[n];
	for (auto &i : a) i = ri();
	struct Query {
		int type;
		int x;
		int y;
	};
	Query qs[q];
	for (auto &i : qs) {
		std::string tmp;
		std::cin >> tmp;
		i.type = tmp[0] == 'B';
		i.x = ri() - 1;
		i.y = ri();
	}
	BIT tree(n + 1);
	for (auto i : qs) if (i.type) {
		tree.add(i.x, 1);
		tree.add(i.y, -1);
	}
	int64_t res[n];
	memset(res, 0, sizeof(res));
	for (int i = 0; i < n; i++) res[i] = (int64_t) a[i] * tree.sum(i + 1);
	for (auto i : qs) {
		if (i.type) {
			tree.add(i.x, -1);
			tree.add(i.y, 1);
		} else res[i.x] += (int64_t) i.y * tree.sum(i.x + 1);
	}
	bool first = true;
	for (auto i : res) {
		if (first) first = false;
		else printf(" ");
		printf("%" PRId64, i);
	}
	puts("");
	return 0;
}
0