Submission #478277

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
478277	2021-10-06T19:17:17 Z	rainboy	NLO (COCI18_nlo)	C	110 / 110	166 ms	8228 KB

nlo

#include <stdio.h>

#define N	100000
#define K	100
#define L	20

int ok(int x, int y, int r) {
	return (long long) x * x + (long long) y * y <= (long long) r * r;
}

int lg[1 << L];

void init() {
	int b, l;

	for (b = 0, l = 0; b < 1 << L; b++) {
		while (1 << l + 1 <= b)
			l++;
		lg[b] = l;
	}
}

int lg_(long long *bb) {
	int h;

	for (h = 4; h >= 0; h--)
		if (bb[h] > 0)
			return h * L + lg[bb[h]];
	return -1;
}

long long bbb[N][5]; int sum;

void upd(int x, int h) {
	sum -= lg_(bbb[x]) + 1;
	bbb[x][h / L] ^= 1 << h % L;
	sum += lg_(bbb[x]) + 1;
}

int main() {
	static int xx[K], yy[K], rr[K], xx1[K], xx2[K];
	int k, n, m, h, y;
	long long ans;

	init();
	scanf("%d%d%d", &n, &m, &k);
	for (h = 0; h < k; h++) {
		scanf("%d%d%d", &xx[h], &yy[h], &rr[h]), xx[h]--, yy[h]--;
		xx1[h] = xx2[h] = xx[h];
	}
	sum = 0, ans = (long long) k * n * m;
	for (y = 0; y < m; y++) {
		for (h = 0; h < k; h++) {
			int d = y - yy[h];

			if (d == -rr[h])
				upd(xx[h], h);
			else if (d == rr[h] + 1)
				upd(xx[h], h);
			else if (d > -rr[h] && d <= rr[h]) {
				while (xx1[h] > 0 && ok(xx1[h] - 1 - xx[h], d, rr[h]))
					upd(--xx1[h], h);
				while (!ok(xx1[h] - xx[h], d, rr[h]))
					upd(xx1[h]++, h);
				while (xx2[h] + 1 < n && ok(xx2[h] + 1 - xx[h], d, rr[h]))
					upd(++xx2[h], h);
				while (!ok(xx2[h] - xx[h], d, rr[h]))
					upd(xx2[h]--, h);
			}
		}
		ans -= sum;
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

nlo.c: In function 'init':
nlo.c:17:17: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   17 |   while (1 << l + 1 <= b)
      |               ~~^~~
nlo.c: In function 'main':
nlo.c:46:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |  scanf("%d%d%d", &n, &m, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
nlo.c:48:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |   scanf("%d%d%d", &xx[h], &yy[h], &rr[h]), xx[h]--, yy[h]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

110.0 / 110.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4432 KB	Output is correct
2	Correct	5 ms	4432 KB	Output is correct
3	Correct	5 ms	4652 KB	Output is correct
4	Correct	13 ms	4520 KB	Output is correct
5	Correct	22 ms	4824 KB	Output is correct
6	Correct	69 ms	6300 KB	Output is correct
7	Correct	53 ms	6128 KB	Output is correct
8	Correct	128 ms	6932 KB	Output is correct
9	Correct	58 ms	7752 KB	Output is correct
10	Correct	166 ms	8228 KB	Output is correct