#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007
#define dancila 3.14159265359
#define eps 1e-9
// #define fisier
using namespace std;
typedef long long ll;
int add(int a, int b)
{
ll x = a+b;
if(x >= mod)
x -= mod;
if(x < 0)
x += mod;
return x;
}
ll mul(ll a, ll b)
{
return (a*b) % mod;
}
ll pw(ll a, ll b)
{
ll ans = 1;
while(b)
{
if(b & 1)
ans = (ans * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return ans;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
long long rand_seed()
{
long long a = rng();
return a;
}
int n, k, val, v[200002], vv[200002], ign[200002];
ll fact[200002], inv[200002];
ll C(int n, int k)
{
return mul(fact[n], mul(inv[k], inv[n-k]));
}
int solve(int val)
{
for(int i = 1; i <= n; ++i)
ign[i] = 0;
for(int i = val; i > 1; --i)
if(v[i] < v[i-1])
ign[i-1] = 1;
for(int i = val; i < n; ++i)
if(v[i] < v[i+1])
ign[i+1] = 1;
int nn = 0;
int st = 0;
int dr = 0;
for(int i = 1; i <= n; ++i)
{
if(!ign[i])
vv[++nn] = v[i];
if(i == val)
st = nn-1, dr = nn+1;
}
int ans = 1;
bool prveq = 0;
int lst = 0;
while(st >= 1 && dr <= nn)
{
if(vv[st] == vv[dr])
{
int xx = st;
while(xx && vv[xx] == vv[st])
--xx;
int yy = dr;
while(yy <= nn && vv[yy] == vv[dr])
++yy;
ans = mul(ans, C(st - xx + yy - dr, st - xx));
prveq = 1;
lst = v[st];
st = xx;
dr = yy;
}
else
if(vv[st] > vv[dr])
{
int xx = st;
while(xx && vv[xx] == vv[st])
--xx;
st = xx;
}
else
{
int yy = dr;
while(yy <= n && vv[yy] == vv[dr])
++yy;
dr = yy;
}
}
return ans;
}
int main()
{
#ifdef fisier
ifstream f("input.in");
ofstream g("output.out");
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> k;
for(int i = 1; i <= n; ++i)
cin >> v[i];
fact[0] = inv[0] = 1;
for(int i = 1; i <= n; ++i)
{
fact[i] = mul(fact[i-1], i);
inv[i] = pw(fact[i], mod - 2);
}
for(; k; --k)
{
cin >> val;
cout << solve(val) << '\n';
}
return 0;
}
Compilation message
zarulje.cpp: In function 'int solve(int)':
zarulje.cpp:78:10: warning: variable 'prveq' set but not used [-Wunused-but-set-variable]
bool prveq = 0;
^~~~~
zarulje.cpp:79:9: warning: variable 'lst' set but not used [-Wunused-but-set-variable]
int lst = 0;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
3320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
