Submission #1230543

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230543		kaiboy	Nuclearia (CEOI15_nuclearia)	C++20	100 / 100	496 ms	316216 KiB

nuclearia

// coached by rainboy
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 2500000;

long long *dd0[N], *dd1[N], ee0[N], ee1[N], *dd[N];

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; i++) {
		dd0[i] = new long long[m];
		dd1[i] = new long long[m];
		dd[i] = new long long[m];
	}
	while (k--) {
		int i, j, a, b; cin >> i >> j >> a >> b, i--, j--;
		int k = a / b, r = a % b, il = max(i - k, 0), jl = max(j - k, 0);
		if (k) {
			int l = min(k, min(n - 1 - i, m - 1 - j));
			dd0[i + l][j + l] += b, dd0[il][jl] -= b;
			dd[0][0] += (long long) b * max(k - max(i, j), 0);
			if (i - (k - 1) >= 0 && j + k < m)
				dd1[i - (k - 1)][j + k] -= b;
			else if (j + i + 2 < m) {
				dd1[0][j + i + 1] -= b, ee0[j + i + 2] -= b;
				if (j + k + 1 < m)
					ee0[j + k + 1] += b;
			} else if (i - (m - 1 - j - 1) < n)
				dd1[i - (m - 1 - j - 1)][m - 1] -= b;
			if (i + k + 1 < n && j - k >= 0)
				dd1[i + k + 1][j - k] += b;
			else if (i + j + 2 < n) {
				ee1[i + j + 2] -= b;
				if (i + k + 1 < n)
					ee1[i + k + 1] += b;
			}
		}
		dd[il][jl] += r;
		if (j + 1 + k < m)
			dd[il][j + 1 + k] -= r;
		if (i + 1 + k < n)
			dd[i + 1 + k][jl] -= r;
		if (i + 1 + k < n && j + 1 + k < m)
			dd[i + 1 + k][j + 1 + k] += r;
	}
	for (int i = n - 1; i >= 0; i--)
		for (int j = m - 1; j >= 0; j--)
			if (i || j)
				dd0[max(i - 1, 0)][max(j - 1, 0)] += dd0[i][j];
	for (int i = 1; i < n; i++)
		for (int j = m - 2; j >= 0; j--)
			dd1[i][j] += dd1[i - 1][j + 1];
	for (int j = 1; j < m; j++)
		ee0[j] += ee0[j - 1];
	for (int j = 0; j < m; j++)
		dd[0][j] += ee0[j];
	for (int i = 1; i < n; i++)
		ee1[i] += ee1[i - 1];
	for (int i = 0; i < n; i++)
		dd[i][0] += ee1[i];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			dd[i][j] += dd0[i][j] + dd1[i][j];
	for (int i = 0; i < n; i++)
		for (int j = 1; j < m; j++)
			dd[i][j] += dd[i][j - 1];
	for (int i = 1; i < n; i++)
		for (int j = 0; j < m; j++)
			dd[i][j] += dd[i - 1][j];
	for (int i = 0; i < n; i++)
		for (int j = 1; j < m; j++)
			dd[i][j] += dd[i][j - 1];
	for (int i = 1; i < n; i++)
		for (int j = 0; j < m; j++)
			dd[i][j] += dd[i - 1][j];
	int t; cin >> t;
	while (t--) {
		int il, jl, ir, jr; cin >> il >> jl >> ir >> jr, il--, jl--, ir--, jr--;
		long long s = dd[ir][jr];
		if (il)
			s -= dd[il - 1][jr];
		if (jl)
			s -= dd[ir][jl - 1];
		if (il && jl)
			s += dd[il - 1][jl - 1];
		long long k = (ir - il + 1) * (jr - jl + 1), 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