oj.uz

Submission #545890

# Submission time Handle Problem Language Result Execution time Memory
545890 2022-04-05T15:55:00 Z rainboy Nuclearia (CEOI15_nuclearia) C
100 / 100
 760 ms 323236 KB 
#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

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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 430 ms 313368 KB Output is correct
2 Correct 85 ms 4544 KB Output is correct
3 Correct 82 ms 3792 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 313384 KB Output is correct
2 Correct 82 ms 4556 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 59380 KB Output is correct
2 Correct 100 ms 4300 KB Output is correct

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 58892 KB Output is correct
2 Correct 87 ms 4512 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 656 ms 319316 KB Output is correct
2 Correct 104 ms 5248 KB Output is correct

Subtask #6
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 131368 KB Output is correct
2 Correct 85 ms 4540 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 64924 KB Output is correct
2 Correct 86 ms 4828 KB Output is correct

Subtask #8
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 68704 KB Output is correct
2 Correct 83 ms 4232 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 760 ms 323236 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 737 ms 323112 KB Output is correct

Subtask #11
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 68840 KB Output is correct
2 Correct 325 ms 68664 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 68596 KB Output is correct
2 Correct 317 ms 68504 KB Output is correct

Subtask #13
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 391 ms 70404 KB Output is correct
2 Correct 348 ms 69112 KB Output is correct

Subtask #14
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 68836 KB Output is correct
2 Correct 331 ms 147020 KB Output is correct