oj.uz

Submission #393024

# Submission time Handle Problem Language Result Execution time Memory
393024 2021-04-22T14:50:17 Z rainboy Relativnost (COCI15_relativnost) C
0 / 140
 2516 ms 22804 KB 
#include <stdio.h>
#include <string.h>

#define N	100000
#define N_	(1 << 17)	/* N_ = pow2(ceil(log2(N))) */
#define K		20
#define MD	10007

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

int st[N_ * 2][K + 1], n_, k;

void pul(int i) {
	int l = i << 1, r = l | 1, a, b;

	memset(st[i], 0, (k + 1) * sizeof *st[i]);
	for (a = 0; a <= k; a++) {
		int x = st[l][a];

		if (x == 0)
			continue;
		for (b = 0; b <= k; b++) {
			int y = st[r][b], c = min(a + b, k);

			if (y == 0)
				continue;
			st[i][c] = (st[i][c] + x * y) % MD;
		}
	}
}

void build(int *aa, int *bb, int n) {
	int i;

	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	for (i = 0; i < n; i++)
		st[n_ + i][0] = bb[i] % MD, st[n_ + i][1] = aa[i] % MD;
	for (i = n_ - 1; i > 0; i--)
		pul(i);
}

void update(int i, int a, int b) {
	i += n_;
	st[i][0] = b % MD, st[i][1] = a % MD;
	while (i > 1)
		pul(i >>= 1);
}

int main() {
	static int aa[N], bb[N];
	int n, q, i;

	scanf("%d%d", &n, &k);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]);
	for (i = 0; i < n; i++)
		scanf("%d", &bb[i]);
	build(aa, bb, n);
	scanf("%d", &q);
	while (q--) {
		int a, b;

		scanf("%d%d%d", &i, &a, &b), i--;
		update(i, a, b);
		printf("%d\n", st[1][k]);
	}
	return 0;
}

Compilation message

relativnost.c: In function 'main':
relativnost.c:55:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   55 |  scanf("%d%d", &n, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~
relativnost.c:57:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   57 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
relativnost.c:59:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   59 |   scanf("%d", &bb[i]);
      |   ^~~~~~~~~~~~~~~~~~~
relativnost.c:61:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   61 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
relativnost.c:65:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   65 |   scanf("%d%d%d", &i, &a, &b), i--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 460 KB Output isn't correct
2 Incorrect 10 ms 460 KB Output isn't correct
3 Incorrect 13 ms 464 KB Output isn't correct
4 Incorrect 330 ms 13360 KB Output isn't correct
5 Incorrect 1060 ms 22636 KB Output isn't correct
6 Incorrect 1496 ms 22804 KB Output isn't correct
7 Incorrect 660 ms 14204 KB Output isn't correct
8 Incorrect 384 ms 22468 KB Output isn't correct
9 Incorrect 739 ms 21980 KB Output isn't correct
10 Incorrect 2516 ms 21272 KB Output isn't correct