Submission #837048

#	Time	Username	Problem	Language	Result	Execution time	Memory
837048		NemanjaSo2005	Matching (CEOI11_mat)	C++17	100 / 100	1494 ms	65536 KiB

mat

#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]*(ll)stepen[i-1]%MOD;
      if(H2<0)
         H2+=MOD;
      H2+=kol[i+N-1]*(ll)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 (stderr)

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++)
      |                ~^~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 8 / 8
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10