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 <cstdio>
#include <cstring>
#include <vector>
#include <stack>
#include <algorithm>
#define PB push_back
using namespace std;
typedef long long ll;
const int N = 2e5 + 500;
const int MOD = 1e9 + 9;
int fak[N], A[N], cnt[N][2], ans[N], n, q, inv[N];
stack < int > L, R;
vector < int > rek[N];
inline int add(int A, int B){
if(A + B >= MOD)
return A + B - MOD;
return A + B;
}
inline int mul(int A, int B){
return (ll)A * B % MOD;
}
inline int pot(int A, int B){
int ret = 1, bs = A;
for(; B ; B >>= 1){
if(B & 1) ret = mul(ret, bs);
bs = mul(bs, bs);
}
return ret;
}
void precompute(){
fak[0] = 1, inv[0] = 1;
for(int i = 1;i < N;i++){
fak[i] = mul(fak[i - 1], i);
}
inv[N - 1] = pot(fak[N - 1], MOD - 2);
for(int i = N - 2; i ; i--)
inv[i] = mul(i + 1, inv[i + 1]);
}
int ch(int n, int k){
return mul(fak[n], mul(inv[n - k], inv[k]));
}
int inv_ch(int n, int k){
return mul(inv[n], mul(fak[n - k], fak[k]));
}
int sol = 1;
void promijeni(int x, int k, int del){
sol = mul(sol,inv_ch(cnt[x][0] + cnt[x][1], cnt[x][0]));
cnt[x][k] += del;
sol = mul(sol, ch(cnt[x][0] + cnt[x][1], cnt[x][0]));
}
int main(){
precompute();
scanf("%d%d", &n, &q);
for(int i = 0;i < n;i++)
scanf("%d", A + i);
for(int i = n - 1;i >= 0;i--){
while(!R.empty() && R.top() > A[i])
rek[i].PB(R.top()), promijeni(R.top(), 1, -1), R.pop();
reverse(rek[i].begin(), rek[i].end());
R.push(A[i]); promijeni(A[i], 1, 1);
}
for(int i = 0;i < n;i++){
promijeni(R.top(), 1, -1); R.pop();
for(int x : rek[i])
R.push(x), promijeni(x, 1, 1);
ans[i] = sol;
while(!L.empty() && L.top() > A[i])
promijeni(L.top(), 0, -1), L.pop();
L.push(A[i]); promijeni(A[i], 0, 1);
}
for(;q--;){
int x; scanf("%d", &x);
printf("%d\n", ans[x - 1]);
}
return 0;
}
Compilation message (stderr)
zarulje.cpp: In function 'int main()':
zarulje.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
67 | scanf("%d%d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~
zarulje.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
69 | scanf("%d", A + i);
| ~~~~~^~~~~~~~~~~~~
zarulje.cpp:86:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
86 | int x; scanf("%d", &x);
| ~~~~~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |