#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"
typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }
void io() {
#ifdef LOCAL_PROJECT
freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else
/* online submission */
#endif
ios_base::sync_with_stdio(false); cin.tie(NULL);
}
const ll MOD = 1000000007LL;
/****************************************************************/
ll pow(ll a, ll p) {
ll ret = 1LL;
while (p) {
if (p & 1LL) ret *= a;
a *= a;
ret %= MOD, a %= MOD;
p >>= 1;
}
return ret;
}
ll inv(ll x) { return pow(x, MOD - 2LL); }
const int MAXN = 200099;
ll fact[MAXN], ifact[MAXN];
void precomp(int n) {
fact[0] = 1;
FORE(i, 1, n) fact[i] = ((ll)i*fact[i - 1]) % MOD;
FORE(i, 0, n) ifact[i] = inv(fact[i]);
}
ll choose(int n, int r) {
assert(n >= r);
return (((fact[n] * ifact[n - r]) % MOD) * ifact[r]) % MOD;
}
ll invchoose(int n, int r) {
assert(n >= r);
return (((fact[r] * fact[n - r]) % MOD) * ifact[n]) % MOD;
}
int N, Q;
int A[MAXN];
int lcnt[MAXN], rcnt[MAXN];
v<pii> changes[MAXN];
ll allans[MAXN];
void initR() {
// precompute right segments
stack<int> st;
RFORE(i, N - 1, 1) {
while (!st.empty() && A[i] < st.top()) {
changes[i].push_back({ st.top(), -1 });
rcnt[st.top()]--;
st.pop();
}
changes[i].push_back({ A[i], 1 });
st.push(A[i]);
rcnt[A[i]]++;
}
}
int main() {
io();
cin >> N >> Q;
FOR(i, 0, N) cin >> A[i];
precomp(N);
initR();
allans[0] = 1;
ll ans = 1;
stack<int> stac;
FOR(i, 1, N) {
v<pii> lchanges;
set<int> changedNums;
// add [i-1] into left
while (!stac.empty() && stac.top() > A[i - 1]) {
lchanges.push_back({ stac.top(), -1 });
changedNums.insert(stac.top());
stac.pop();
}
lchanges.push_back({ A[i - 1], 1 });
stac.push(A[i - 1]);
// remove [i] from right
for (pii &c : changes[i]) changedNums.insert(c.first);
for (int x : changedNums) {
ans *= invchoose(lcnt[x] + rcnt[x], lcnt[x]);
ans %= MOD;
}
for (pii &c : lchanges)
lcnt[c.first] += c.second;
for (pii &c : changes[i])
rcnt[c.first] -= c.second;
for (int x : changedNums) {
ans *= choose(lcnt[x] + rcnt[x], lcnt[x]);
ans %= MOD;
}
allans[i] = ans;
}
FOR(i, 0, Q) {
int p;
cin >> p;
p--;
cout << allans[p] << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5240 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
12176 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5240 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
