Submission #486384

#	Time	Username	Problem	Language	Result	Execution time	Memory
486384		rainboy	Žarulje (COI15_zarulje)	C11	100 / 100	106 ms	42676 KiB

zarulje

#include <stdio.h>
#include <stdlib.h>

#define N	200000
#define MD	1000000007

unsigned int X = 12345;

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

int vv[N + 1], ff[N + 1], gg[N + 1];

void init() {
	int i;

	ff[0] = gg[0] = 1;
	for (i = 1; i <= N; i++) {
		vv[i] = i == 1 ? 1 : (long long) vv[i - MD % i] * (MD / i + 1) % MD;
		ff[i] = (long long) ff[i - 1] * i % MD;
		gg[i] = (long long) gg[i - 1] * vv[i] % MD;
	}
}

int choose(int n, int k) {
	return (long long) ff[n] * gg[k] % MD * gg[n - k] % MD;
}

int vchoose(int n, int k) {
	return (long long) gg[n] * ff[k] % MD * ff[n - k] % MD;
}

int main() {
	static int aa[N], qu[N], cc[N], nxt[N], *qul[N], *ccl[N], kkl[N], *qur[N], *ccr[N], kkr[N], ans[N], dd[N];
	int n, q, h, hl, hr, i, j, cnt;

	init();
	scanf("%d%d", &n, &q);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]);
	cnt = 0;
	for (i = 0; i < n; i++) {
		int cnt_ = cnt;

		while (cnt && aa[qu[cnt - 1]] > aa[i])
			cnt--;
		if (cnt == 0 || aa[qu[cnt - 1]] != aa[i]) {
			kkl[i] = cnt_ - cnt;
			qul[i] = (int *) malloc(kkl[i] * sizeof *qul[i]);
			ccl[i] = (int *) malloc(kkl[i] * sizeof *ccl[i]);
			for (h = cnt; h < cnt_; h++)
				qul[i][cnt_ - 1 - h] = qu[h], ccl[i][cnt_ - 1 - h] = cc[h];
			qu[cnt] = i, cc[cnt] = 1, cnt++;
		} else {
			kkl[i] = cnt_ - cnt + 1;
			qul[i] = (int *) malloc(kkl[i] * sizeof *qul[i]);
			ccl[i] = (int *) malloc(kkl[i] * sizeof *ccl[i]);
			for (h = cnt - 1; h < cnt_; h++)
				qul[i][cnt_ - 1 - h] = qu[h], ccl[i][cnt_ - 1 - h] = cc[h];
			qu[cnt - 1] = i, cc[cnt - 1]++;
		}
	}
	cnt = 0;
	for (i = n - 1; i >= 0; i--) {
		int cnt_ = cnt;

		while (cnt && aa[qu[cnt - 1]] > aa[i])
			cnt--;
		nxt[i] = cnt == 0 ? n : qu[cnt - 1];
		if (cnt == 0 || aa[qu[cnt - 1]] != aa[i]) {
			kkr[i] = cnt_ - cnt;
			qur[i] = (int *) malloc(kkr[i] * sizeof *qur[i]);
			ccr[i] = (int *) malloc(kkr[i] * sizeof *ccr[i]);
			for (h = cnt; h < cnt_; h++)
				qur[i][cnt_ - 1 - h] = qu[h], ccr[i][cnt_ - 1 - h] = cc[h];
			qu[cnt] = i, cc[cnt] = 1, cnt++;
		} else {
			kkr[i] = cnt_ - cnt + 1;
			qur[i] = (int *) malloc(kkr[i] * sizeof *qur[i]);
			ccr[i] = (int *) malloc(kkr[i] * sizeof *ccr[i]);
			for (h = cnt - 1; h < cnt_; h++)
				qur[i][cnt_ - 1 - h] = qu[h], ccr[i][cnt_ - 1 - h] = cc[h];
			qu[cnt - 1] = i, cc[cnt - 1]++;
		}
	}
	for (i = 0; i < n; i++)
		ans[i] = 1;
	for (i = 0; i < n; i++) {
		hl = 0, hr = 0;
		while (hl < kkl[i] && hr < kkr[i])
			if (aa[qul[i][hl]] > aa[qur[i][hr]])
				hl++;
			else if (aa[qul[i][hl]] < aa[qur[i][hr]])
				hr++;
			else {
				ans[i] = (long long) ans[i] * choose(ccl[i][hl] + ccr[i][hr], ccl[i][hl]) % MD;
				hl++, hr++;
			}
	}
	for (i = 0; i < n; i++)
		dd[i] = 1;
	for (i = 0; i < n; i++)
		if (kkl[i] == 0 || aa[qul[i][kkl[i] - 1]] != aa[i]) {
			int c = kkr[i] == 0 || aa[qur[i][kkr[i] - 1]] != aa[i] ? 0 : ccr[i][kkr[i] - 1];

			for (h = 0, j = i; h < c; h++, j = nxt[j]) {
				dd[j + 1] = (long long) dd[j + 1] * choose(c + 1, h + 1) % MD;
				dd[nxt[j]] = (long long) dd[nxt[j]] * vchoose(c + 1, h + 1) % MD;
			}
		}
	for (i = 1; i < n; i++)
		dd[i] = (long long) dd[i] * dd[i - 1] % MD;
	for (i = 1; i < n; i++)
		ans[i] = (long long) ans[i] * dd[i] % MD;
	while (q--) {
		scanf("%d", &i), i--;
		printf("%d\n", ans[i]);
	}
	return 0;
}

Compilation message (stderr)

zarulje.c: In function 'main':
zarulje.c:39:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |  scanf("%d%d", &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
zarulje.c:41:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
zarulje.c:117:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |   scanf("%d", &i), i--;
      |   ^~~~~~~~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 38 / 38
• Subtask 3: 40 / 40