結果

問題 No.865 24時間降水量
ユーザー MarcusAureliusAntoninus
提出日時 2019-08-16 22:13:18
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,613 bytes
コンパイル時間 2,654 ms
コンパイル使用メモリ 196,140 KB
最終ジャッジ日時 2025-01-07 12:19:55
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 TLE * 3
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:42:36: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 2 has type ‘long int*’ [-Wformat=]
   42 |         for (auto& e: A) scanf("%lld", &e);
      |                                 ~~~^   ~~
      |                                    |   |
      |                                    |   long int*
      |                                    long long int*
      |                                 %ld
main.cpp:60:29: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 3 has type ‘int64_t*’ {aka ‘long int*’} [-Wformat=]
   60 |                 scanf("%d%lld", &T, &V);
      |                          ~~~^       ~~
      |                             |       |
      |                             |       int64_t* {aka long int*}
      |                             long long int*
      |                          %ld
main.cpp:66:28: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘int64_t’ {aka ‘long int’} [-Wformat=]
   66 |                 printf("%lld\n", max);
      |                         ~~~^     ~~~
      |                            |     |
      |                            |     int64_t {aka long int}
      |                            long long int
      |                         %ld
main.cpp:40:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   40 |         scanf("%d", &N);
      |         ~~~~~^~~~~~~~~~
main.cpp:42:31: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   42 |         for (auto& e: A) scanf("%lld", &e);
      |                          ~~~~~^~~~~~~~~~~~
main.cpp:55:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’

ソースコード

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;
	scanf("%d", &N);
	std::vector<int64_t> A(N);
	for (auto& e: A) scanf("%lld", &e);
	RSumQBIT rsq(N);
	for (int i{}; i < N; i++)
		rsq.update(i, A[i]);

	std::vector<int64_t> sum(N + 1);
	for (int i{}; i < N; i++)
		sum[i + 1] = sum[i] + A[i];
	int64_t max{};
	for (int i{}; i + 24 <= N; i++)
		max = std::max(max, sum[i + 24] - sum[i]);
	
	int Q;
	scanf("%d", &Q);
	for (int loop{}; loop < Q; loop++)
	{
		int T;
		int64_t V;
		scanf("%d%lld", &T, &V);
		T--;
		rsq.update(T, V - A[T]);
		A[T] = V;
		for (int left{std::max(0, T - 23)}; left + 24 <= N; left++)
			max = std::max(max, rsq.get(left, left + 24));
		printf("%lld\n", max);
	}

	return 0;
}
0