Submission #393025

#	Time	Username	Problem	Language	Result	Execution time	Memory
393025		rainboy	Relativnost (COCI15_relativnost)	C11	140 / 140	2621 ms	22988 KiB

relativnost

#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; i < n_; i++)
		st[n_ + i][0] = 1;
	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 (stderr)

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

• Subtask 1: 140 / 140