#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int MOD = 1e9+7;
const int MAXN = 2e5+4;
int powers[MAXN];
int dp[MAXN];
int int_open[MAXN];
int int_close[MAXN];
int ans[MAXN];
int fac[MAXN];
int facinv[MAXN];
pii cur_space[MAXN];
int n, q;
int expo(ll a, int b) {
ll res = 1;
while (b > 0) {
if (b & 1) {
res *= a;
res %= MOD;
}
b >>= 1;
a *= a;
a %= MOD;
}
return res;
}
int c(int n, int k) {
ll cur = fac[n];
cur *= facinv[k];
cur %= MOD;
cur *= facinv[n-k];
return (cur%MOD);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n >> q;
n += 2;
fac[0] = 1;
ll cur = 1;
facinv[0] = 1;
for (int i = 1; i <= n; i++) {
cur *= i;
cur %= MOD;
fac[i] = cur;
facinv[i] = expo(fac[i], MOD-2);
}
powers[0] = 0;
powers[n-1] = 0;
vector<pii> proc_order;
for (int i = 1; i < n-1; i++) {
cin >> powers[i];
assert(powers[i] > 0);
proc_order.push_back(pii(powers[i], i));
}
fill(int_open, int_open+n, -1);
fill(int_close, int_close+n, -1);
int_open[0] = int_close[n-1] = 0;
sort(proc_order.begin(), proc_order.end());
set<int> completed_vals;
dp[0] = dp[n-1] = 1;
completed_vals.insert(0);
completed_vals.insert(n-1);
for (int r = 0; r < n-2;) {
vector<int> to_add;
vector<int> extra_consid;
int l = r;
while (r < n-2 && proc_order[l].first == proc_order[r].first) r++;
for (int curr = l; curr < r;) {
int curl = curr;
auto it = completed_vals.upper_bound(proc_order[curl].second);
int rp = *it;
it--;
int lp = *it;
vector<int> cur_posses;
while (curr < r && *completed_vals.upper_bound(proc_order[curr].second) == rp) {
cur_posses.push_back(proc_order[curr].second);
to_add.push_back(proc_order[curr].second);
curr++;
}
cur_space[rp].first = cur_space[lp].second = cur_posses.size();
extra_consid.push_back(lp);
extra_consid.push_back(rp);
for (int p = 0; p < cur_posses.size()-1; p++) {
int i = cur_posses[p];
int_open[i] = i;
int_close[cur_posses[p+1]] = i;
ll curdp = dp[lp];
curdp *= c(cur_posses.size(), p+1);
curdp %= MOD;
dp[i] = curdp;
curdp = dp[lp];
curdp *= c(cur_posses.size()-1, p);
curdp %= MOD;
ans[i] = curdp;
}
}
for (int m: extra_consid) {
if (cur_space[m].first != 0 && cur_space[m].second != 0) {
auto it = completed_vals.lower_bound(m);
int lp = *(--it);
ll curdp = dp[lp];
curdp *= c(cur_space[m].first+cur_space[m].second, cur_space[m].first);
curdp %= MOD;
ans[m] = curdp;
}
cur_space[m] = pii(0, 0);
}
for (int v: to_add) completed_vals.insert(v);
}
vector<int> stck;
stck.push_back(0);
for (int i = 1; i < n-1; i++) {
if (int_close[i] >= 0) stck.pop_back();
if (!ans[i]) ans[i] = dp[stck.back()];
if (int_open[i] >= 0) stck.push_back(int_open[i]);
}
for (int i = 0; i < q; i++) {
int x; cin >> x;
cout << ans[x] << "\n";
}
}
Compilation message
zarulje.cpp: In function 'int main()':
zarulje.cpp:91:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for (int p = 0; p < cur_posses.size()-1; p++) {
| ~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
95 ms |
9296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
