結果

問題 No.3265 地元に帰れば天才扱い！
ユーザー elphe
提出日時 2025-08-08 11:14:48
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,989 bytes
コンパイル時間 4,296 ms
コンパイル使用メモリ 277,644 KB
実行使用メモリ 814,620 KB
最終ジャッジ日時 2025-09-06 12:31:15
合計ジャッジ時間 10,117 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3 RE * 1
other MLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

namespace MyLib
{
	static inline constexpr uint_fast32_t ceil_sqrt(uint_fast64_t a) noexcept
	{
		uint_fast32_t ans = (UINT64_C(1) << (__CHAR_BIT__ * std::min(sizeof(uint_fast32_t), sizeof(uint_fast64_t) / 2))) - 1;
		for (char i = __CHAR_BIT__ * std::min(sizeof(uint_fast32_t), sizeof(uint_fast64_t) / 2) - 1; i >= 0; --i)
		{
			const uint_fast32_t temp = ans ^ (1u << i);
			if (static_cast<uint_fast64_t>(temp) * (temp) >= a)
				ans = temp;
		}

		return ans;
	}

	static inline constexpr uint_fast32_t ceil_div(const uint_fast32_t a, const uint_fast32_t b) noexcept
	{
		return (a + b - 1) / b;
	}
}

// imos 配列を先頭から区間合計値取得して、一点の重みを得る
static inline constexpr uint_fast32_t get_weight(const uint_fast32_t index, const uint_fast32_t section_length_of_imos, const std::vector<uint_fast32_t>& imos_weight, const std::vector<uint_fast32_t>& section_sum_imos)
{
	uint_fast32_t weight = 0, i;
	for (i = 0; (i + 1) * section_length_of_imos <= index + 1; ++i)
		weight += section_sum_imos[i];
	for (i *= section_length_of_imos; i <= index; ++i)
		weight += imos_weight[i];
	
	return weight;
}

// 平方分割配列から区間合計値取得する
static inline constexpr uint_fast64_t get_range_sum(uint_fast32_t first, const uint_fast32_t end, const uint_fast32_t section_length_of_A, const std::vector<uint_fast32_t>& A, const std::vector<uint_fast64_t>& section_sum_A)
{
	uint_fast64_t range_sum = 0;
	if (first / section_length_of_A == end / section_length_of_A)
		for (; first != end; ++first)
			range_sum += A[first];
	else
	{
		for (; first % section_length_of_A != 0; ++first)
			range_sum += A[first];
		for (; (first + section_length_of_A) <= end; first += section_length_of_A)
			range_sum += section_sum_A[first / section_length_of_A];
		for (; first < end; ++first)
			range_sum += A[first];
	}

	return range_sum;
}

// 平方分割解法
static inline std::vector<uint_fast64_t> solve(const uint_fast32_t N, const uint_fast32_t Q, std::vector<uint_fast32_t>& A, const std::vector<uint_fast32_t>& X, const std::vector<uint_fast32_t>& Y, const std::vector<uint_fast32_t>& L, const std::vector<uint_fast32_t>& R)
{
	const uint_fast32_t section_length_of_A = MyLib::ceil_sqrt(N), section_length_of_imos = MyLib::ceil_sqrt(N + 1);
	std::vector<uint_fast32_t> imos_weight(N + 1, 0), section_sum_imos(MyLib::ceil_div(N + 1, section_length_of_imos), 0);
	std::vector<uint_fast64_t> ans(Q), section_sum_A(MyLib::ceil_div(N, section_length_of_A), 0);
	for (uint_fast32_t i = 0; i != N; ++i)
		section_sum_A[i / section_length_of_A] += A[i];

	std::cout << section_length_of_imos << std::endl;

	uint_fast64_t sum = 0;
	for (uint_fast32_t i = 0; i != Q; ++i)
	{
		const uint_fast32_t weight = get_weight(X[i] - 1, section_length_of_imos, imos_weight, section_sum_imos);
		sum -= static_cast<uint_fast64_t>(A[X[i] - 1]) * weight, section_sum_A[(X[i] - 1) / section_length_of_A] -= static_cast<uint_fast64_t>(A[X[i] - 1]);
		A[X[i] - 1] = Y[i];
		sum += static_cast<uint_fast64_t>(Y[i]) * weight, section_sum_A[(X[i] - 1) / section_length_of_A] += static_cast<uint_fast64_t>(Y[i]);
		sum += get_range_sum(L[i] - 1, R[i], section_length_of_A, A, section_sum_A);
		++imos_weight[L[i] - 1], --imos_weight[R[i]], ++section_sum_imos[(L[i] - 1) / section_length_of_imos], --section_sum_imos[R[i] / section_length_of_imos];
		ans[i] = sum;
	}

	return ans;
}

static inline void output(const uint_fast32_t Q, const std::vector<uint_fast64_t>& ans) noexcept
{
	for (uint_fast32_t i = 0; i != Q; ++i)
		std::cout << ans[i] << '\n';
}

int main()
{
	std::cin.tie(nullptr);
	std::ios::sync_with_stdio(false);

	uint_fast32_t N, Q, i;
	std::cin >> N;
	std::vector<uint_fast32_t> A(N);
	for (i = 0; i != N; ++i)
		std::cin >> A[i];

	std::cin >> Q;
	std::vector<uint_fast32_t> X(Q), Y(Q), L(Q), R(Q);
	for (i = 0; i != Q; ++i)
		std::cin >> X[i] >> Y[i] >> L[i] >> R[i];

	output(Q, solve(N, Q, A, X, Y, L, R));
	return 0;
}
0