oj.uz

Submission #740608

# Submission time Handle Problem Language Result Execution time Memory
740608 2023-05-12T19:14:02 Z rainboy A Game with Grundy (CCO20_day1problem1) C
25 / 25
 79 ms 4872 KB 
#include <stdio.h>

#define N	100000

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

unsigned int Z = 12345;

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

int xx[N * 2];

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)
			if (xx[ii[j]] == xx[i_])
				j++;
			else if (xx[ii[j]] < xx[i_]) {
				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 * 2], kk[N + 1];
	int n, l, r, y, i, d;

	scanf("%d%d%d%d", &n, &l, &r, &y);
	for (i = 0; i < n; i++) {
		int x, dx, dy;

		scanf("%d%d%d", &x, &dy, &dx);
		xx[i << 1 | 0] = max(l, x - (long long) (y * dx + dy - 1) / dy + 1);
		xx[i << 1 | 1] = min(r, x + (long long) (y * dx + dy - 1) / dy - 1) + 1;
	}
	for (i = 0; i < n * 2; i++)
		ii[i] = i;
	sort(ii, 0, n * 2);
	kk[0] += xx[ii[0]] - l;
	for (i = 0, d = 0; i + 1 < n * 2; i++) {
		d += (ii[i] & 1) == 0 ? 1 : -1;
		kk[d] += xx[ii[i + 1]] - xx[ii[i]];
	}
	kk[0] += r + 1 - xx[ii[n * 2 - 1]];
	for (d = 1; d <= n; d++)
		kk[d] += kk[d - 1];
	for (d = 0; d <= n; d++)
		printf("%d\n", kk[d]);
	return 0;
}

Compilation message

Main.c: In function 'main':
Main.c:39:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |  scanf("%d%d%d%d", &n, &l, &r, &y);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:43:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |   scanf("%d%d%d", &x, &dy, &dx);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.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 59 ms 4092 KB Output is correct
4 Correct 62 ms 4232 KB Output is correct
5 Correct 59 ms 4168 KB Output is correct
6 Correct 48 ms 3648 KB Output is correct
7 Correct 47 ms 3692 KB Output is correct
8 Correct 1 ms 300 KB Output is correct

Subtask #2
10.0 / 10.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 59 ms 4092 KB Output is correct
4 Correct 62 ms 4232 KB Output is correct
5 Correct 59 ms 4168 KB Output is correct
6 Correct 48 ms 3648 KB Output is correct
7 Correct 47 ms 3692 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 59 ms 4660 KB Output is correct
10 Correct 71 ms 4872 KB Output is correct
11 Correct 60 ms 4856 KB Output is correct
12 Correct 79 ms 4664 KB Output is correct
13 Correct 49 ms 4012 KB Output is correct