Submission #545890

#	Time	Username	Problem	Language	Result	Execution time	Memory
545890		rainboy	Nuclearia (CEOI15_nuclearia)	C11	100 / 100	760 ms	323236 KiB

nuclearia

#include <stdio.h>
#include <stdlib.h>

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int main() {
	long long **aa, *bb, *cc, **dd, **ee;
	int n, m, q, i, j;

	scanf("%d%d%d", &n, &m, &q);
	aa = (long long **) malloc((n + 1) * sizeof *aa);
	bb = (long long *) calloc(m + 1, sizeof *bb);
	cc = (long long *) calloc(n + 1, sizeof *cc);
	dd = (long long **) malloc((n + 1) * sizeof *dd);
	ee = (long long **) malloc((n + 1) * sizeof *ee);
	for (i = 0; i <= n; i++) {
		aa[i] = (long long *) calloc(m + 1, sizeof *aa[i]);
		dd[i] = (long long *) calloc(m + 1, sizeof *dd[i]);
		ee[i] = (long long *) calloc(m + 1, sizeof *ee[i]);
	}
	while (q--) {
		int a, b, c, c_;

		scanf("%d%d%d%d", &i, &j, &a, &b), i--, j--;
		c = a / b;
		aa[max(i - c, 0)][max(j - c, 0)] += a % b, aa[max(i - c, 0)][min(j + c + 1, m)] -= a % b;
		aa[min(i + c + 1, n)][max(j - c, 0)] -= a % b, aa[min(i + c + 1, n)][min(j + c + 1, m)] += a % b;
		if (c == 0)
			continue;

		if (max(i, j) < c - 1)
			aa[0][0] += (long long) b * (c - 1 - max(i, j));
		if (i < min(j, c - 1))
			bb[max(j - c + 1, 0)] += b, bb[j - i] -= b;
		if (j < min(i, c - 1))
			cc[max(i - c + 1, 0)] += b, cc[i - j] -= b;
		c_ = min(min(i, j), c - 1);
		dd[i - c_][j - c_] += b, dd[i + 1][j + 1] -= b;

		if (i < min(m - 2 - j, c - 1))
			bb[j + i + 2] -= b, bb[min(j + c + 1, m)] += b;
		c_ = min(min(i, m - 2 - j), c - 1);
		if (c_ >= 0)
			ee[i - c_][j + c_ + 1] -= b, ee[i + 1][j] += b;

		if (j < min(n - 2 - i, c - 1))
			cc[i + j + 2] -= b, cc[min(i + c + 1, n)] += b;
		c_ = min(min(n - 2 - i, j), c - 1);
		if (c_ >= 0) {
			ee[i + 1][j] -= b;
			if (j > c_)
				ee[i + c_ + 2][j - c_ - 1] += b;
		}

		c_ = min(min(n - 2 - i, m - 2 - j), c - 1);
		if (c_ >= 0)
			dd[i + 1][j + 1] += b, dd[i + c_ + 2][j + c_ + 2] -= b;
	}
	for (j = 1; j < m; j++)
		bb[j] += bb[j - 1];
	for (j = 0; j < m; j++)
		aa[0][j] += bb[j];
	for (i = 1; i < n; i++)
		cc[i] += cc[i - 1];
	for (i = 0; i < n; i++)
		aa[i][0] += cc[i];
	for (i = 1; i < n; i++)
		for (j = 1; j < m; j++)
			dd[i][j] += dd[i - 1][j - 1];
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			aa[i][j] += dd[i][j];
	for (i = 1; i < n; i++)
		for (j = 0; j < m - 1; j++)
			ee[i][j] += ee[i - 1][j + 1];
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			aa[i][j] += ee[i][j];
	for (i = 0; i < n; i++)
		for (j = 1; j < m; j++)
			aa[i][j] += aa[i][j - 1];
	for (j = 0; j < m; j++)
		for (i = 1; i < n; i++)
			aa[i][j] += aa[i - 1][j];
	for (i = 0; i < n; i++)
		for (j = 1; j < m; j++)
			aa[i][j] += aa[i][j - 1];
	for (j = 0; j < m; j++)
		for (i = 1; i < n; i++)
			aa[i][j] += aa[i - 1][j];
	scanf("%d", &q);
	while (q--) {
		int i1, j1, i2, j2;
		long long sum, area;

		scanf("%d%d%d%d", &i1, &j1, &i2, &j2), i1--, j1--, i2--, j2--;
		sum = aa[i2][j2] - (j1 == 0 ? 0 : aa[i2][j1 - 1]) - (i1 == 0 ? 0 : aa[i1 - 1][j2]) + (i1 == 0 || j1 == 0 ? 0 : aa[i1 - 1][j1 - 1]);
		area = (long long) (i2 - i1 + 1) * (j2 - j1 + 1);
		printf("%lld\n", (sum + area / 2) / area);
	}
	return 0;
}

Compilation message (stderr)

nuclearia.c: In function 'main':
nuclearia.c:11:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |  scanf("%d%d%d", &n, &m, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
nuclearia.c:25:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   scanf("%d%d%d%d", &i, &j, &a, &b), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
nuclearia.c:92:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
nuclearia.c:97:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |   scanf("%d%d%d%d", &i1, &j1, &i2, &j2), i1--, j1--, i2--, j2--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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