oj.uz

Submission #393025

# Submission time Handle Problem Language Result Execution time Memory
393025 2021-04-22T14:51:15 Z rainboy Relativnost (COCI15_relativnost) C
140 / 140
 2621 ms 22988 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; 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

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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 460 KB Output is correct
2 Correct 9 ms 472 KB Output is correct
3 Correct 15 ms 464 KB Output is correct
4 Correct 357 ms 11736 KB Output is correct
5 Correct 1079 ms 22760 KB Output is correct
6 Correct 1598 ms 22988 KB Output is correct
7 Correct 756 ms 11816 KB Output is correct
8 Correct 378 ms 22596 KB Output is correct
9 Correct 729 ms 22968 KB Output is correct
10 Correct 2621 ms 22912 KB Output is correct