Submission #1229613

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229613		kaiboy	Nuclearia (CEOI15_nuclearia)	C++20	100 / 100	825 ms	499308 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() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	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;
		dd[0][0] += (long long) b * max(k - max(i, j), 0);
		ddne[i][j + 1] -= b, ddne[il][jr] += b;
		dd[0][m + 1] -= (long long) b * max(k - max(i, m + 1 - j), 0);
		ddsw[i + 1][j] -= b, ddsw[ir][jl] += b;
		dd[n + 1][0] -= (long long) b * max(k - max(n + 1 - i, j), 0);
		ddse[i + 1][j + 1] += b, ddse[ir][jr] -= b;
		dd[n + 1][m + 1] += (long long) b * max(k - max(n + 1 - i, m + 1 - j), 0);
		dd[il][jl] += r, dd[il][jr] -= r, dd[ir][jl] -= r, dd[ir][jr] += r;
	}
	for (int i = n + 1; i >= 0; i--)
		for (int j = m + 1; j >= 0; j--)
			if (i || j)
				ddnw[max(i - 1, 0)][max(j - 1, 0)] += ddnw[i][j];
	for (int i = n + 1; i >= 0; i--)
		for (int j = 0; j <= m + 1; j++)
			if (i || j <= m)
				ddne[max(i - 1, 0)][min(j, m) + 1] += ddne[i][j];
	for (int i = 0; i <= n + 1; i++)
		for (int j = m + 1; j >= 0; j--)
			if (i <= n || j)
				ddsw[min(i, n) + 1][max(j - 1, 0)] += ddsw[i][j];
	for (int i = 0; i <= n + 1; i++)
		for (int j = 0; j <= m + 1; j++)
			if (i <= n || j <= n)
				ddse[min(i, n) + 1][min(j, m) + 1] += ddse[i][j];
	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: 3 / 3
• Subtask 2: 2 / 2
• Subtask 3: 3 / 3
• Subtask 4: 2 / 2
• Subtask 5: 6 / 6
• Subtask 6: 4 / 4
• Subtask 7: 6 / 6
• Subtask 8: 4 / 4
• Subtask 9: 15 / 15
• Subtask 10: 10 / 10
• Subtask 11: 15 / 15
• Subtask 12: 10 / 10
• Subtask 13: 12 / 12
• Subtask 14: 8 / 8