#include<bits/stdc++.h>
#define ll long long
using namespace std;
int N,K,M,niz[1000005],oduz[1000005],kol[1000005],H,H2;
int MOD=1000000009,b=1000003,stepen[1000005];
vector<vector<int>> on,off;
vector<int> R;
struct cvor{
int cnt,mlt,rez=-1;
};
bool porez(cvor a,cvor b){
return a.rez<b.rez;
}
const int base=38;
cvor st[2142000];
cvor opr(cvor a,cvor b){
if(a.rez==-1)
return b;
if(b.rez==-1)
return a;
a.rez=(a.rez+b.rez+(ll)a.cnt*b.mlt)%MOD;
a.mlt+=b.mlt;
if(a.mlt>=MOD)
a.mlt-=MOD;
a.cnt+=b.cnt;
return a;
}
void update(int gde,bool akt){
if(akt==false){
st[gde].rez=-1;
}
else
st[gde].rez=0;
// cout<<gde<<endl;
gde=(gde+base-2)/base;
while(gde){
//cout<<gde<<endl;
st[gde]=st[gde*base-base+2];
for(int i=-base+3;i<=1;i++){
// cout<<gde*base+i<<" ";
st[gde]=opr(st[gde],st[gde*base+i]);
}
// cout<<endl;
gde=(gde+base-2)/base;
}
}
void fadd(int poz,int kol){
for(int i=poz;i<=M;i+=i&(-i))
st[i].cnt+=kol;
return;
}
int fsum(int gde){
int ret=0;
for(int i=gde;i>=1;i-=i&(-i))
ret+=st[i].cnt;
return ret;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>N>>M;
K=1;
int upok=1;
while(K<2*M){
upok+=K;
K*=base;
}
on.resize(M+5);
off.resize(M+5);
stepen[0]=1;
for(int i=1;i<=M;i++)
stepen[i]=(stepen[i-1]*(ll)b)%MOD;
int a;
for(int i=1;i<=N;i++){
cin>>a;
niz[a]=i;
}
for(int i=1;i<=N;i++){
fadd(niz[i],1);
H=(H+((ll)i-fsum(niz[i]))*stepen[i])%MOD;
}
for(int i=1;i<=M;i++)
cin>>niz[i];
for(int i=1;i<=M;i++){
st[i].mlt=i;
st[i].rez=niz[i];
}
sort(st+1,st+1+M,porez);
for(int i=1;i<=M;i++)
niz[st[i].mlt]=i;
for(int i=1;i<=M;i++)
st[i].cnt=0;
for(int i=1;i<=M;i++){
fadd(niz[i],1);
kol[i]=i-fsum(niz[i]);
}
for(int i=1;i<=M;i++)
niz[i]=st[i].mlt;
for(int i=1;i<=M;i++){
st[i].cnt=0;
st[i].mlt=0;
st[i].rez=-1;
}
for(int i=M;i>=1;i--){
st[upok].cnt=1;
st[upok].mlt=0;
st[upok].rez=-1;
on[niz[i]].push_back(upok);
upok++;
st[upok].cnt=0;
st[upok].mlt=stepen[niz[i]];
st[upok].rez=-1;
int l=max(1,niz[i]-N);
on[l].push_back(upok);
off[niz[i]].push_back(upok);
upok++;
}
for(int i=1;i<=M;i++){
for(int j=0;j<on[i].size();j++)
update(on[i][j],true);
for(int j=0;j<off[i].size();j++)
update(off[i][j],false);
oduz[i]=st[1].rez;
}
for(int i=1;i<=N;i++)
H2=(H2+(ll)kol[i]*stepen[i])%MOD;
if(H2==H)
R.push_back(1);
for(int i=2;i+N-1<=M;i++){
H=(H*(ll)b)%MOD;
H2-=(ll)kol[i-1]*stepen[i-1]%MOD;
if(H2<0)
H2+=MOD;
H2+=(ll)kol[i+N-1]*stepen[i+N-1]%MOD;
if(H2>=MOD)
H2-=MOD;
int tmp=H2-oduz[i-1];
if(tmp<0)
tmp+=MOD;
if(H==tmp)
R.push_back(i);
}
cout<<R.size()<<"\n";
for(int i=0;i<R.size();i++)
cout<<R[i]<<" ";
cout<<"\n";
return 0;
}
Compilation message
mat.cpp: In function 'int main()':
mat.cpp:125:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
125 | for(int j=0;j<on[i].size();j++)
| ~^~~~~~~~~~~~~
mat.cpp:127:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | for(int j=0;j<off[i].size();j++)
| ~^~~~~~~~~~~~~~
mat.cpp:151:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
151 | for(int i=0;i<R.size();i++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
25428 KB |
Output is correct |
| 2 |
Correct |
9 ms |
25428 KB |
Output is correct |
| 3 |
Correct |
10 ms |
25428 KB |
Output is correct |
| 4 |
Correct |
10 ms |
25428 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
25556 KB |
Output is correct |
| 2 |
Correct |
11 ms |
25556 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
27860 KB |
Output is correct |
| 2 |
Correct |
36 ms |
27604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
28016 KB |
Output is correct |
| 2 |
Correct |
38 ms |
27988 KB |
Output is correct |
| 3 |
Correct |
13 ms |
25824 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
333 ms |
48264 KB |
Output is correct |
| 2 |
Correct |
331 ms |
49604 KB |
Output is correct |
| 3 |
Correct |
567 ms |
50656 KB |
Output is correct |
| 4 |
Correct |
573 ms |
50636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
379 ms |
51020 KB |
Output is correct |
| 2 |
Correct |
549 ms |
50568 KB |
Output is correct |
| 3 |
Correct |
369 ms |
50192 KB |
Output is correct |
| 4 |
Correct |
290 ms |
52680 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
398 ms |
50720 KB |
Output is correct |
| 2 |
Correct |
374 ms |
50292 KB |
Output is correct |
| 3 |
Correct |
404 ms |
50208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
30 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
28 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
30 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
26 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
