Submission #784089

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
784089	2023-07-15T16:19:26 Z	rainboy	Lightning Rod (NOI18_lightningrod)	C	66 / 100	2000 ms	226632 KB

lightningrod

#include <stdio.h>

#define N	10000000
#define INF	0x3f3f3f3f

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int ll[N], rr[N];

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k) {
			int c = ll[ii[j]] != ll[i_] ? ll[ii[j]] - ll[i_] : rr[i_] - rr[ii[j]];

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
		}
		}
		sort(ii, l, i);
		l = k;
	}
}

int main() {
	static int ii[N];
	int n, i, x, y, r, cnt;

	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d%d", &x, &y);
		ll[i] = x - y, rr[i] = x + y;
	}
	for (i = 0; i < n; i++)
		ii[i] = i;
	sort(ii, 0, n);
	r = -INF, cnt = 0;
	for (i = 0; i < n; i++)
		if (r < rr[ii[i]])
			r = rr[ii[i]], cnt++;
	printf("%d\n", cnt);
	return 0;
}

Compilation message

lightningrod.c: In function 'main':
lightningrod.c:40:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
lightningrod.c:42:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |   scanf("%d%d", &x, &y);
      |   ^~~~~~~~~~~~~~~~~~~~~

Subtask #1

0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2078 ms	226632 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	288 KB	Output is correct
4	Correct	0 ms	292 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct

Subtask #3

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	288 KB	Output is correct
4	Correct	0 ms	292 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	296 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct

Subtask #4

21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	288 KB	Output is correct
4	Correct	0 ms	292 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	296 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct

Subtask #5

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	288 KB	Output is correct
4	Correct	0 ms	292 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	296 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	68 ms	6012 KB	Output is correct
15	Correct	53 ms	5808 KB	Output is correct
16	Correct	44 ms	5180 KB	Output is correct

Subtask #6

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2019 ms	213344 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #7

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2078 ms	226632 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-