Submission #1229610

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229610		kaiboy	Nuclearia (CEOI15_nuclearia)	C++20	25 / 100	1096 ms	491112 KiB

nuclearia

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 2500000;

long long *ddnw[N + 2], *ddne[N + 2], *ddsw[N + 2], *ddse[N + 2], *dd[N + 2];

int main() {
	int n, m, k; cin >> n >> m >> k;
	for (int i = 0; i <= n + 1; i++) {
		ddnw[i] = new long long[m + 2];
		ddne[i] = new long long[m + 2];
		ddsw[i] = new long long[m + 2];
		ddse[i] = new long long[m + 2];
		dd[i] = new long long[m + 2];
	}
	while (k--) {
		int i, j, a, b; cin >> i >> j >> a >> b;
		int k = a / b, r = a % b;
		int il = max(i - k, 0), ir = min(i + 1 + k, n + 1);
		int jl = max(j - k, 0), jr = min(j + 1 + k, m + 1);
		ddnw[i][j] += b;
		ddnw[il][jl] -= b;
		ddne[i][j + 1] -= b;
		ddne[il][jr] += b;
		ddsw[i + 1][j] -= b;
		ddsw[ir][jl] += b;
		ddse[i + 1][j + 1] += b;
		ddse[ir][jr] -= b;
		dd[il][jl] += r;
		dd[il][jr] -= r;
		dd[ir][jl] -= r;
		dd[ir][jr] += r;
	}
	for (int i = n; i >= 0; i--)
		for (int j = m; j >= 0; j--)
			ddnw[i][j] += ddnw[i + 1][j + 1];
	for (int i = n; i >= 0; i--)
		for (int j = 1; j <= m + 1; j++)
			ddne[i][j] += ddne[i + 1][j - 1];
	for (int i = 1; i <= n + 1; i++)
		for (int j = m; j >= 0; j--)
			ddsw[i][j] += ddsw[i - 1][j + 1];
	for (int i = 1; i <= n + 1; i++)
		for (int j = 1; j <= m + 1; j++)
			ddse[i][j] += ddse[i - 1][j - 1];
	for (int i = 0; i <= n + 1; i++)
		for (int j = 0; j <= m + 1; j++)
			dd[i][j] += ddnw[i][j] + ddne[i][j] + ddsw[i][j] + ddse[i][j];
	for (int i = 0; i <= n + 1; i++)
		for (int j = 1; j <= m + 1; j++)
			dd[i][j] += dd[i][j - 1];
	for (int i = 1; i <= n + 1; i++)
		for (int j = 0; j <= m + 1; j++)
			dd[i][j] += dd[i - 1][j];
	for (int i = 0; i <= n + 1; i++)
		for (int j = 1; j <= m + 1; j++)
			dd[i][j] += dd[i][j - 1];
	for (int i = 1; i <= n + 1; i++)
		for (int j = 0; j <= m + 1; j++)
			dd[i][j] += dd[i - 1][j];
	int q; cin >> q;
	while (q--) {
		int il, jl, ir, jr; cin >> il >> jl >> ir >> jr, il--, jl--;
		long long s = dd[ir][jr] - dd[ir][jl] - dd[il][jr] + dd[il][jl];
		long long k = (ir - il) * (jr - jl), q = s / k, r = s % k;
		if (r >= (k + 1) / 2)
			q++;
		cout << q << '\n';
	}
	return 0;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 2
• Subtask 3: 0 / 3
• Subtask 4: 0 / 2
• Subtask 5: 0 / 6
• Subtask 6: 0 / 4
• Subtask 7: 0 / 6
• Subtask 8: 0 / 4
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10
• Subtask 11: 15 / 15
• Subtask 12: 10 / 10
• Subtask 13: 0 / 12
• Subtask 14: 0 / 8