Submission #244305

#TimeUsernameProblemLanguageResultExecution timeMemory
244305TadijaSebezMatching (CEOI11_mat)C++11
100 / 100
894 ms44268 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...