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>
using namespace std;
#define ll long long
#define pb push_back
const int N=1000050;
const int base=7777777;
const int mod=998244353;
int add(int x,int y){x+=y;return x>=mod?x-mod:x;}
int sub(int x,int y){x-=y;return x<0?x+mod:x;}
int mul(int x,int y){return (ll)x*y%mod;}
int powmod(int x,int k){
int ans=1;
for(;k;k>>=1,x=mul(x,x))if(k&1)ans=mul(ans,x);
return ans;
}
int inv(int x){return powmod(x,mod-2);}
int dvd(int x,int y){return mul(x,inv(y));}
int pw[N];
/*const int M=2*N;
int ls[M],rs[M],tsz,root,sum[M],num[M],lzy[M];
void Build(int&c,int ss,int se){
c=++tsz;lzy[c]=1;
if(ss==se)return;
int mid=ss+se>>1;
Build(ls[c],ss,mid);
Build(rs[c],mid+1,se);
}
void push(int c){
if(lzy[c]!=1){
sum[ls[c]]=mul(sum[ls[c]],lzy[c]);
sum[rs[c]]=mul(sum[rs[c]],lzy[c]);
lzy[ls[c]]=mul(lzy[ls[c]],lzy[c]);
lzy[rs[c]]=mul(lzy[rs[c]],lzy[c]);
lzy[c]=1;
}
}
void Set(int c,int ss,int se,int qi,int f,int x){
if(ss==se){
sum[c]=x;
num[c]=f;
return;
}
push(c);
int mid=ss+se>>1;
if(qi<=mid)Set(ls[c],ss,mid,qi,f,x);
else Set(rs[c],mid+1,se,qi,f,x);
sum[c]=add(sum[ls[c]],sum[rs[c]]);
num[c]=num[ls[c]]+num[rs[c]];
}
void Mul(int c,int ss,int se,int qs,int qe,int x){
if(qs>qe||qs>se||ss>qe)return;
if(qs<=ss&&qe>=se){lzy[c]=mul(lzy[c],x);sum[c]=mul(sum[c],x);return;}
int mid=ss+se>>1;
push(c);
Mul(ls[c],ss,mid,qs,qe,x);
Mul(rs[c],mid+1,se,qs,qe,x);
sum[c]=add(sum[ls[c]],sum[rs[c]]);
num[c]=num[ls[c]]+num[rs[c]];
}
int Get(int c,int ss,int se,int qs,int qe){
if(qs>qe||qs>se||ss>qe)return 0;
if(qs<=ss&&qe>=se)return sum[c];
int mid=ss+se>>1;
push(c);
return add(Get(ls[c],ss,mid,qs,qe),Get(rs[c],mid+1,se,qs,qe));
}
int GetCnt(int c,int ss,int se,int qs,int qe){
if(qs>qe||qs>se||ss>qe)return 0;
if(qs<=ss&&qe>=se)return num[c];
int mid=ss+se>>1;
push(c);
return GetCnt(ls[c],ss,mid,qs,qe)+GetCnt(rs[c],mid+1,se,qs,qe);
}*/
int leaf[N],has[N],ml=1,dv=1,root,ibase;
void Build(int&c,int ss,int se){}
void Set(int c,int ss,int se,int qi,int f,int x){
x=mul(x,ml);
for(int i=qi;i<N;i+=i&-i){
leaf[i]=add(leaf[i],x);
has[i]+=f?1:-1;
}
}
void Mul(int c,int ss,int se,int qs,int qe,int x){
ml=mul(ml,base);
dv=mul(dv,ibase);
}
int Get(int c,int ss,int se,int qs,int qe){
int ans=0;
for(int i=qe;i;i-=i&-i)ans=add(ans,leaf[i]);
for(int i=qs-1;i;i-=i&-i)ans=sub(ans,leaf[i]);
return mul(ans,dv);
}
int GetCnt(int c,int ss,int se,int qs,int qe){
int ans=0;
for(int i=qe;i;i-=i&-i)ans+=has[i];
for(int i=qs-1;i;i-=i&-i)ans-=has[i];
return ans;
}
//int leaf[N],has[N];
void Ins(int x,int f){
Set(root,1,N-1,x,1,f);
//has[x]=1;
//leaf[x]=f;
}
void Ers(int x,int f){
Set(root,1,N-1,x,0,sub(0,Get(root,1,N-1,x,x)));
//has[x]=0;
//leaf[x]=f;
}
void Dvd(int l,int r,int f){
//f=inv(f);
Mul(root,1,N-1,l,r,f);
//for(int i=l;i<=r;i++)leaf[i]=mul(leaf[i],f);
}
int Get(int l,int r){
return Get(root,1,N-1,l,r);
//int ans=0;
//for(int i=l;i<=r;i++)ans=add(ans,leaf[i]);
//return ans;
}
int GetCnt(int l,int r){
return GetCnt(root,1,N-1,l,r);
//int ans=0;
//for(int i=l;i<=r;i++)ans+=has[i];
//return ans;
}
int hsh,cnt;
void Add(int x){
hsh=add(hsh,Get(x+1,N-1));
Ins(x,pw[cnt]);
hsh=add(hsh,mul(GetCnt(1,x),pw[cnt]));
cnt++;
}
void Del(int x){
int tmp=GetCnt(1,x);
hsh=sub(hsh,tmp);
Ers(x,0);
hsh=mul(hsh,ibase);
Dvd(1,N-1,base);
hsh=sub(hsh,Get(x+1,N-1));
cnt--;
}
int a[N],b[N],p[N];
int main(){
pw[0]=1;for(int i=1;i<N;i++)pw[i]=mul(pw[i-1],base);ibase=inv(base);
Build(root,1,N-1);
int n,m;scanf("%i %i",&n,&m);
for(int i=1;i<=n;i++)scanf("%i",&a[i]),p[a[i]]=i;
int goal=0;
for(int i=n;i>=1;i--)goal=add(mul(goal,base),p[i]);
vector<int> all;
for(int i=1;i<=m;i++)scanf("%i",&b[i]),all.pb(b[i]);
sort(all.begin(),all.end());
for(int i=1;i<=m;i++)b[i]=lower_bound(all.begin(),all.end(),b[i])-all.begin()+1;
for(int i=1;i<n;i++)Add(b[i]);
vector<int> ans;
for(int i=n;i<=m;i++){
Add(b[i]);
//printf("%i %i\n",hsh,goal);
if(hsh==goal)ans.pb(i-n+1);
Del(b[i-n+1]);
}
printf("%i\n",ans.size());
for(int i:ans)printf("%i ",i);
return 0;
}
Compilation message (stderr)
mat.cpp: In function 'int main()':
mat.cpp:168:26: warning: format '%i' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
printf("%i\n",ans.size());
~~~~~~~~~~^
mat.cpp:151:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int n,m;scanf("%i %i",&n,&m);
~~~~~^~~~~~~~~~~~~~~
mat.cpp:152:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=n;i++)scanf("%i",&a[i]),p[a[i]]=i;
~~~~~~~~~~~~~~~~~^~~~~~~~~~
mat.cpp:156:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=m;i++)scanf("%i",&b[i]),all.pb(b[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... |