#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
#define MASK(n) (1 << (n))
#define BIT(mask,x) ((mask >> (x)) & 1)
#define TASK "task"
using namespace std;
const int mxN = 5e5 + 7;
const int base = 512;
const int inf = 1e9 + 6969;
const int Mod = 1e6 + 3;
const long long infll = 1e18 + 6969;
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
struct MST {
int n;
vector<int>par;
MST(int _n) {
n = _n;
par.assign(n + 2,-1);
}
int get_root(int u) {
if(par[u] < 0) return u;
return par[u] = get_root(par[u]);
}
void merge(int u,int v) {
u = get_root(u);
v = get_root(v);
if(u == v) return;
if(par[u] > par[v]) swap(u,v);
par[u] += par[v];
par[v] = u;
}
};
int n;
int k;
int a[mxN];
int bit[mxN];
int adj[mxN];
int frac[mxN];
int Pow(int n,int k) {
if(k == 1) return n % Mod;
ll tmp = Pow(n,(k >> 1)) % Mod;
tmp = (tmp * tmp) % Mod;
if(k & 1) tmp = (tmp * n) % Mod;
return tmp;
}
void fractorize() {
frac[0] = 1;
for(int i = 1;i < mxN;i++)
frac[i] = (1LL * frac[i - 1] * i) % Mod;
adj[mxN] = Pow(frac[mxN],Mod - 2);
for(int i = mxN - 1;i > 0;i--)
adj[i - 1] = (1LL * adj[i] * i) % Mod;
}
int Ckn(int k,int n) {
if(k > n) return 0LL;
return 1LL * (frac[n] * adj[k] % Mod * adj[n - k] % Mod);
}
void solve() {
cin >> n >> k;
fractorize();
for (int i = 1; i <= n - k + 1; i++) cin >> a[i];
memset(bit,-1,sizeof bit);
MST dsu(n + 2);
for (int i = 1; i <= n - k; i++) {
if(a[i] < a[i + 1]) {
int u = dsu.get_root(i);
int v = dsu.get_root(i + k);
bit[u] = 0;
bit[v] = 1;
}
if(a[i] > a[i + 1]) {
int u = dsu.get_root(i);
int v = dsu.get_root(i + k);
bit[u] = 1;
bit[v] = 0;
}
else dsu.merge(i,i + k);
}
int cnt = 0;
for (int i = 1; i <= k; i++) {
int u = dsu.get_root(i);
if(bit[u] < 0) cnt++;
else a[1] -= bit[u];
}
cout << Ckn(a[1],cnt);
}
signed main() {
ios_base :: sync_with_stdio(0);
cin.tie(0);
//freopen(TASK".inp","r",stdin);
//freopen(TASK".out","w",stdout);
int tc = 1;
//cin >> tc;
while(tc--) {
solve();
}
}
Compilation message
Main.cpp: In function 'void fractorize()':
Main.cpp:70:19: warning: array subscript 500007 is above array bounds of 'int [500007]' [-Warray-bounds]
70 | adj[mxN] = Pow(frac[mxN],Mod - 2);
| ~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:56:5: note: while referencing 'frac'
56 | int frac[mxN];
| ^~~~
Main.cpp:70:12: warning: array subscript 500007 is above array bounds of 'int [500007]' [-Warray-bounds]
70 | adj[mxN] = Pow(frac[mxN],Mod - 2);
| ~~~~~~~^
Main.cpp:55:5: note: while referencing 'adj'
55 | int adj[mxN];
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
6748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
6748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
6748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
6748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
6748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
6748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
