#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e6+5;
int MOD=1e9+9,b=1e6+3;
int N,K,M,H,H2,kol[maxn],fwt[maxn],niz[maxn],stepen[maxn];
pair<int,int> sniz[maxn];
vector<int> R;
void fadd(int gde,int kol){
for(int i=gde;i<=M;i+=i&-i)
fwt[i]+=kol;
return;
}
int fget(int gde){
int ret=0;
for(int i=gde;i>=1;i-=i&-i)
ret+=fwt[i];
return ret;
}
struct cvor{
int rez,mlt,cur;
}c1,c2,st[2100000];
cvor opr(cvor a,cvor b){
a.rez=(a.rez+b.rez+(ll)a.cur*b.mlt)%MOD;
a.cur+=b.cur;
a.mlt+=b.mlt;
if(a.mlt>=MOD)
a.mlt-=MOD;
return a;
}
void prop(int gde){
st[gde*2]=opr(st[gde*2],st[gde]);
st[gde*2+1]=opr(st[gde*2+1],st[gde]);
st[gde].rez=0;
st[gde].mlt=0;
st[gde].cur=0;
}
void update(int lg,int dg,cvor sta,int gde=1,int lc=1,int dc=K){
if(lg==lc and dg==dc){
st[gde]=opr(st[gde],sta);
return;
}
prop(gde);
int sred=(lc+dc)/2;
if(dg<=sred)
return update(lg,dg,sta,gde*2,lc,sred);
if(lg>sred)
return update(lg,dg,sta,gde*2+1,sred+1,dc);
update(lg,sred,sta,gde*2,lc,sred);
update(sred+1,dg,sta,gde*2+1,sred+1,dc);
return;
}
void add(int l,int r){
if(r<l)
return;
cvor x;
x.mlt=0;
x.rez=0;
x.cur=1;
update(l,r,x);
}
void multi(int l,int r,int kol){
if(r<l)
return;
cvor x;\
x.rez=0;
x.cur=0;
x.mlt=kol;
update(l,r,x);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
stepen[0]=1;
N=1e6;
for(int i=1;i<=N;i++)
stepen[i]=stepen[i-1]*(ll)b%MOD;
cin>>N>>M;
K=1;
while(K<M)
K<<=1;
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-fget(niz[i]))*stepen[i])%MOD;
}
for(int i=1;i<=M;i++)
cin>>niz[i];
for(int i=1;i<=M;i++){
sniz[i].first=niz[i];
sniz[i].second=i;
}
sort(sniz+1,sniz+1+M);
for(int i=1;i<=M;i++)
niz[sniz[i].second]=i;
memset(fwt,0,sizeof(fwt));
for(int i=1;i<=M;i++){
fadd(niz[i],1);
kol[i]=i-fget(niz[i]);
}
for(int i=M;i>=1;i--){
int p=sniz[i].second;
add(p,M);
multi(max(1,p-N),p-1,stepen[p]);
}
for(int i=1;i<K;i++)
prop(i);
for(int i=1;i<=N;i++)
H2=(H2+(ll)kol[i]*stepen[i])%MOD;
if(H==H2)
R.push_back(1);
for(int i=2;i+N-1<=M;i++){
H=(H*(ll)b)%MOD;
H2-=kol[i-1]*stepen[i-1]%MOD;
if(H2<0)
H2+=MOD;
H2+=kol[i+N-1]*stepen[i+N-1]%MOD;
if(H2>=MOD)
H2-=MOD;
int tmp=H2-st[K+i-2].rez;
if(tmp<0)
tmp+=MOD;
if(tmp==H)
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:131:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | for(int i=0;i<R.size();i++)
| ~^~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
11 ms |
8276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
11 ms |
8148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
28 ms |
9212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
26 ms |
9240 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
185 ms |
17060 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
217 ms |
17360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
211 ms |
17264 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1229 ms |
58332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1077 ms |
57684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1172 ms |
56220 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1110 ms |
56320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
