#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);
}
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));
}
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(); 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: 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;
if (powers[lp] == powers[m]) curdp = skip_dp[lp];
else 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);
}
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";
}
Compilation message
zarulje.cpp: In function 'int main()':
zarulje.cpp:95:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for (int p = 0; p < cur_posses.size(); p++) {
| ~~^~~~~~~~~~~~~~~~~~~
zarulje.cpp:105:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | if (p < cur_posses.size()-1) {
| ~~^~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
117 ms |
8836 KB |
Output is correct |
| 2 |
Incorrect |
181 ms |
17896 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
