結果

問題 No.877 Range ReLU Query
コンテスト
ユーザー MarcusAureliusAntoninus
提出日時 2019-09-06 22:41:31
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 145 ms / 2,000 ms
コード長 1,950 bytes
コンパイル時間 2,621 ms
コンパイル使用メモリ 201,736 KB
最終ジャッジ日時 2025-01-07 16:54:16
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:47:27: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 2 has type ‘int64_t*’ {aka ‘long int*’} [-Wformat=]
   47 |                 scanf("%lld", &a);
      |                        ~~~^   ~~
      |                           |   |
      |                           |   int64_t* {aka long int*}
      |                           long long int*
      |                        %ld
main.cpp:53:27: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 2 has type ‘int64_t*’ {aka ‘long int*’} [-Wformat=]
   53 |                 scanf("%lld%lld%lld%lld", &com, &l, &r, &x);
      |                        ~~~^               ~~~~
      |                           |               |
      |                           long long int*  int64_t* {aka long int*}
      |                        %ld
main.cpp:53:31: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 3 has type ‘int64_t*’ {aka ‘long int*’} [-Wformat=]
   53 |                 scanf("%lld%lld%lld%lld", &com, &l, &r, &x);
      |                            ~~~^                 ~~
      |                               |                 |
      |                               long long int*    int64_t* {aka long int*}
      |                            %ld
main.cpp:53:35: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 4 has type ‘int64_t*’ {aka ‘long int*’} [-Wformat=]
   53 |                 scanf("%lld%lld%lld%lld", &com, &l, &r, &x);
      |                                ~~~^                 ~~
      |                                   |                 |
      |                                   long long int*    int64_t* {aka long int*}
      |                                %ld
main.cpp:53:39: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 5 has type ‘int64_

ソースコード

diff # 

#include <bits/stdc++.h>

///////////////////////////
// Range Sum Query (BIT) //
///////////////////////////

class RSumQBIT {
private:
	std::vector<int64_t> container_;

	int64_t getHelper(const int index) const
	{
		if (index < 0) return 0;
		if ((int)(container_.size()) <= index) return container_.back();
		int64_t sum{};
		for (int add_place{index}; add_place > 0; add_place -= add_place & -add_place)
			sum += container_[add_place];
		return sum;
	}

public:
	RSumQBIT(const int array_size)
		: container_(array_size + 1) {}
	// indexは0-indexed
	void update(const int index, const int64_t added)
	{
		for (int update_place{index + 1}; update_place < (int)(container_.size()); update_place += update_place & -update_place)
			container_[update_place] += added;
	}
	// left,rightは0-indexed、[left, right)の半開区間
	int64_t get(const int left, const int right) const
	{
		return -getHelper(left) + getHelper(right);
	}
};

int main()
{
	int N, Q;
	scanf("%d%d", &N, &Q);
	std::vector<std::array<int64_t, 5>> queries(N + Q);
	// {1, l, r, x}
	// {2, index, a}
	for (int64_t i{}; i < N; i++)
	{
		int64_t a;
		scanf("%lld", &a);
		queries[i] = {2ll, i, i, a, i};
	}
	for (int i{}; i < Q; i++)
	{
		int64_t com, l, r, x;
		scanf("%lld%lld%lld%lld", &com, &l, &r, &x);
		l--;
		queries[N + i] = {com, l, r, x, i};
	}

	std::sort(queries.begin(), queries.end(), [](auto& a, auto& b) { return a[3] > b[3]; });

	RSumQBIT sum(N), exist(N);
	std::vector<int64_t> ans(Q);
	for (auto& query: queries)
	{
		// for (int i{}; i < N; i++)
		// 	printf("%lld ", sum.get(i, i + 1));
		// putchar('\n');
		// for (int i{}; i < N; i++)
		// 	printf("%lld ", exist.get(i, i + 1));
		// putchar('\n');
		if (query[0] == 1)
			ans[query[4]] = sum.get(query[1], query[2]) - exist.get(query[1], query[2]) * query[3];
		else
		{
			sum.update(query[1], query[3]);
			exist.update(query[1], 1);
		}
	}
	for (auto& e: ans)
		printf("%lld\n", e);

	return 0;
}
0