This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int N,K,M,patern[1000005],niz[1000005],oduz[1000005],kol[1000005],H,H2;
int MOD=1000000009,b=1000003,stepen[1000005];
vector<int> on[1000005],off[1000005],R;
struct slog{
int sv,poz;
} sniz[1000005];
bool posv(slog a,slog b){
return a.sv<b.sv;
}
struct cvor{
int cnt,mlt,rez;
bool on;
}st[4200000];
cvor opr(cvor a,cvor b){
if(a.on==false)
return b;
if(b.on==false)
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){
st[gde].on=akt;
gde/=2;
while(gde){
st[gde]=opr(st[gde*2],st[gde*2+1]);
gde/=2;
}
}
int fwt[1000005];
void fadd(int poz,int kol){
for(int i=poz;i<=M;i+=i&(-i))
fwt[i]+=kol;
return;
}
int fsum(int gde){
int ret=0;
for(int i=gde;i>=1;i-=i&(-i))
ret+=fwt[i];
return ret;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>N>>M;
stepen[0]=1;
for(int i=1;i<=M;i++)
stepen[i]=(stepen[i-1]*(ll)b)%MOD;
K=1;
while(K<2*M)
K<<=1;
for(int i=1;i<=N;i++)
cin>>niz[i];
for(int i=1;i<=N;i++)
sniz[niz[i]].sv=i;
for(int i=1;i<=N;i++)
niz[i]=sniz[i].sv;
/*cout<<"MENI JE"<<endl;
for(int i=1;i<=N;i++)
cout<<niz[i]<<" ";
cout<<endl;*/
for(int i=1;i<=N;i++){
fadd(niz[i],1);
//cout<<i-fsum(niz[i])<<" ";
H=(H+((ll)i-fsum(niz[i]))*stepen[i])%MOD;
}
//cout<<endl;
for(int i=1;i<=M;i++)
cin>>niz[i];
for(int i=1;i<=M;i++){
sniz[i].poz=i;
sniz[i].sv=niz[i];
}
sort(sniz+1,sniz+1+M,posv);
for(int i=1;i<=M;i++)
niz[sniz[i].poz]=i;
int upok=K;
for(int i=M;i>=1;i--){
st[upok].cnt=1;
st[upok].mlt=0;
st[upok].rez=0;
on[sniz[i].poz].push_back(upok);
upok++;
st[upok].cnt=0;
st[upok].mlt=stepen[sniz[i].poz];
st[upok].rez=0;
st[upok].on=false;
int l=max(1,sniz[i].poz-N);
on[l].push_back(upok);
off[sniz[i].poz].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;
// cout<<oduz[i]<<" ";
}
// cout<<endl;
for(int i=1;i<=M;i++)
fwt[i]=0;
for(int i=1;i<=M;i++){
fadd(niz[i],1);
kol[i]=i-fsum(niz[i]);
//cout<<kol[i]<<" ";
}
// cout<<endl;
for(int i=1;i<=N;i++)
H2=(H2+(ll)kol[i]*stepen[i])%MOD;
//cout<<H<<" "<<H2<<endl;
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;
// cout<<i<<" "<<H<<" "<<H2<<endl;
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;
}
/*
5 10
2 1 5 3 4
5 6 3 8 12 7 1 10 11 9
*/
Compilation message (stderr)
mat.cpp: In function 'int main()':
mat.cpp:102:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | for(int j=0;j<on[i].size();j++)
| ~^~~~~~~~~~~~~
mat.cpp:104:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for(int j=0;j<off[i].size();j++)
| ~^~~~~~~~~~~~~~
mat.cpp:139:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
139 | for(int i=0;i<R.size();i++)
| ~^~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |