Submission #836975

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

mat

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int N,K,M,niz[1000005],oduz[1000005],kol[1000005],H,H2;
int MOD=1000000009,b=1000003;
vector<int> on[1005],off[1005];
ll stepen(int koji){
   if(koji==1)
      return b;
   if(koji==0)
      return 1;
   ll ret=stepen(koji/2);
   ret=(ret*ret)%MOD;
   if(koji&1)
      ret=(ret*b)%MOD;
   return ret;
}
int Q=0;
pair<int,int> sniz[3000005];
void dodaj(int poz,int pupd,bool sta){
   pupd+=(!sta)*1e8;
   Q++;
   sniz[Q].first=poz;
   sniz[Q].second=pupd;
}
vector<int> R;
struct cvor{
   int cnt,mlt,rez=-1;
};
bool porez(cvor a,cvor b){
   return a.rez<b.rez;
}
const int base=38;
cvor st[2142000];
cvor opr(cvor a,cvor b){
   if(a.rez==-1)
      return b;
   if(b.rez==-1)
      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=true;
   if(gde>=1e8){
      gde-=1e8;
      akt=false;
   }
   if(akt==false){
      st[gde].rez=-1;
   }
   else
      st[gde].rez=0;
  // cout<<gde<<endl;
   gde=(gde+base-2)/base;
   while(gde){
      //cout<<gde<<endl;
      st[gde]=st[gde*base-base+2];
      for(int i=-base+3;i<=1;i++){
        // cout<<gde*base+i<<" ";
         st[gde]=opr(st[gde],st[gde*base+i]);
      }
     // cout<<endl;
      gde=(gde+base-2)/base;
   }
}
void fadd(int poz,int kol){
   for(int i=poz;i<=M;i+=i&(-i))
      st[i].cnt+=kol;
   return;
}
int fsum(int gde){
   int ret=0;
   for(int i=gde;i>=1;i-=i&(-i))
      ret+=st[i].cnt;
   return ret;
}
int main(){
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   /*cout<<sizeof(st)<<endl;
   cout<<sizeof(sniz)<<endl;
   cout<<sizeof(niz)+sizeof(oduz)+sizeof(kol)<<endl;
   return 0;*/
   cin>>N>>M;
   K=1;
   int upok=1;
   while(K<2*M){
      upok+=K;
      K*=base;
   }
   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-fsum(niz[i]))*stepen(i))%MOD;
   }

   for(int i=1;i<=M;i++)
      cin>>niz[i];
   for(int i=1;i<=M;i++){
      st[i].mlt=i;
      st[i].rez=niz[i];
   }
   sort(st+1,st+1+M,porez);
   for(int i=1;i<=M;i++)
      niz[st[i].mlt]=i;
   for(int i=1;i<=M;i++)
      st[i].cnt=0;
   for(int i=1;i<=M;i++){
      fadd(niz[i],1);
      kol[i]=i-fsum(niz[i]);
   }
   for(int i=1;i<=M;i++)
      niz[i]=st[i].mlt;
   for(int i=1;i<=M;i++){
      st[i].cnt=0;
      st[i].mlt=0;
      st[i].rez=-1;
   }

   for(int i=M;i>=1;i--){
      st[upok].cnt=1;
      st[upok].mlt=0;
      st[upok].rez=-1;
      dodaj(niz[i],upok,true);
      on[niz[i]].push_back(upok);
      upok++;

      st[upok].cnt=0;
      st[upok].mlt=stepen(niz[i]);
      st[upok].rez=-1;
      int l=max(1,niz[i]-N);
      dodaj(l,upok,true);
      dodaj(niz[i],upok,false);
      on[l].push_back(upok);
      off[niz[i]].push_back(upok);
      upok++;
   }
   sort(sniz+1,sniz+1+Q);
   int pok=0;
   sniz[Q+1].first=M+1;
   for(int i=1;i<=M;i++){
      //cout<<i<<endl;
      while(sniz[pok+1].first<=i){
         pok++;
         update(sniz[pok].second);
        // cout<<sniz[pok].second<<" ";
      }/*
      cout<<endl;
      for(int j=0;j<off[i].size();j++){
         update(off[i][j]);
         cout<<off[i][j]<<" ";
      }
      for(int j=0;j<on[i].size();j++){
         update(on[i][j]+1e8);
         cout<<on[i][j]+(int)1e8<<" ";
      }
      cout<<endl;*/
      oduz[i]=st[1].rez;
   }

   for(int i=1;i<=N;i++)
      H2=(H2+(ll)kol[i]*stepen(i))%MOD;
   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;
      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;
}

Compilation message (stderr)

mat.cpp: In function 'int main()':
mat.cpp:189:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  189 |    for(int i=0;i<R.size();i++)
      |                ~^~~~~~~~~

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