#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 skip_dp[MAXN];
int ans[MAXN];
int fac[MAXN];
int facinv[MAXN];
pii cur_space[MAXN];
int n, q;
int bash(pii range) {
if (range == pii(1, n-2)) return 1;
if (powers[range.first-1] == powers[range.second+1])
return (bash(pii(range.first-1, range.second))+bash(pii(range.first, range.second+1)) % MOD);
if (powers[range.first-1] > powers[range.second+1]) return bash(pii(range.first-1, range.second));
return bash(pii(range.first, range.second+1));
}
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);
}
void solve() {
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));
}
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;
vector<int> skip_calc;
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++;
}
if (rp < n-1) skip_calc.push_back(cur_posses.back());
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(); p++) {
int i = cur_posses[p];
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;
if (p < cur_posses.size()-1) {
curdp = dp[lp];
curdp *= c(cur_posses.size()-1, p+1);
curdp %= MOD;
skip_dp[i] = curdp;
}
}
}
for (int m: skip_calc) {
auto it = completed_vals.lower_bound(m);
int rp = *it;
int lp = *(--it);
ll curdp;
if (powers[lp] >= powers[rp]) curdp = skip_dp[lp];
else curdp = dp[lp];
curdp *= c(cur_space[rp].first+cur_space[rp].second, cur_space[rp].first);
skip_dp[m] = (curdp % MOD);
}
for (int v: extra_consid) cur_space[v] = pii(0, 0);
for (int v: to_add) completed_vals.insert(v);
}
for (int i = 1; i < n-1; i++) {
if (powers[i-1] < powers[i]) ans[i] = dp[i-1];
else ans[i] = skip_dp[i-1];
}
bool fail = 0;
for (int i = 0; i < q; i++) {
int x; cin >> x;
// int b = bash(pii(x, x));
cout << ans[x] << /*" " << b << */"\n";
// if (b != ans[x]) fail = 1;
}
if (fail) cout << "FAIL\n";
}
void gen_case() {
for (int i = 1; i <= n; i++) powers[i] = 1+(rand()%3);
}
int main() {
solve();
return 0;
srand(time(0));
while (1) {
n = 10;
gen_case();
solve();
for (int i = 1; i < n-1; i++) {
int b = bash(pii(i, i));
if (b != ans[i]) {
for (int i = 0; i < n; i++) {
cout << powers[i+1] << " ";
}
cout << endl;
exit(0);
}
}
}
}
Compilation message
zarulje.cpp: In function 'void solve()':
zarulje.cpp:97:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for (int p = 0; p < cur_posses.size(); p++) {
| ~~^~~~~~~~~~~~~~~~~~~
zarulje.cpp:107:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | if (p < cur_posses.size()-1) {
| ~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| 3 |
Correct |
2 ms |
468 KB |
Output is correct |
| 4 |
Correct |
3 ms |
472 KB |
Output is correct |
| 5 |
Correct |
2 ms |
468 KB |
Output is correct |
| 6 |
Correct |
3 ms |
476 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
126 ms |
8892 KB |
Output is correct |
| 2 |
Correct |
156 ms |
17780 KB |
Output is correct |
| 3 |
Correct |
224 ms |
17504 KB |
Output is correct |
| 4 |
Correct |
278 ms |
18364 KB |
Output is correct |
| 5 |
Correct |
296 ms |
18460 KB |
Output is correct |
| 6 |
Correct |
325 ms |
18604 KB |
Output is correct |
| 7 |
Correct |
313 ms |
18684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| 3 |
Correct |
2 ms |
468 KB |
Output is correct |
| 4 |
Correct |
3 ms |
472 KB |
Output is correct |
| 5 |
Correct |
2 ms |
468 KB |
Output is correct |
| 6 |
Correct |
3 ms |
476 KB |
Output is correct |
| 7 |
Correct |
126 ms |
8892 KB |
Output is correct |
| 8 |
Correct |
156 ms |
17780 KB |
Output is correct |
| 9 |
Correct |
224 ms |
17504 KB |
Output is correct |
| 10 |
Correct |
278 ms |
18364 KB |
Output is correct |
| 11 |
Correct |
296 ms |
18460 KB |
Output is correct |
| 12 |
Correct |
325 ms |
18604 KB |
Output is correct |
| 13 |
Correct |
313 ms |
18684 KB |
Output is correct |
| 14 |
Correct |
11 ms |
1364 KB |
Output is correct |
| 15 |
Correct |
140 ms |
10836 KB |
Output is correct |
| 16 |
Correct |
195 ms |
21472 KB |
Output is correct |
| 17 |
Correct |
243 ms |
19664 KB |
Output is correct |
| 18 |
Correct |
287 ms |
21556 KB |
Output is correct |
| 19 |
Correct |
312 ms |
19596 KB |
Output is correct |
| 20 |
Correct |
360 ms |
20352 KB |
Output is correct |
| 21 |
Correct |
318 ms |
20456 KB |
Output is correct |
