This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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]);
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--;
| ^~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |