oj.uz

Submission #836940

# Submission time Handle Problem Language Result Execution time Memory
836940 2023-08-24T17:35:48 Z NemanjaSo2005 Matching (CEOI11_mat) C++17
63 / 100
 294 ms 65536 KB 
#include<bits/stdc++.h>
#define ll long long
#pragma GCC target("avx2")
using namespace std;
int N,K,M,niz[1000005],oduz[1000005],kol[1000005],H,H2;
int MOD=1000000009,b=1000003,stepen[1000005];
vector<vector<int>> on,off;
vector<int> R;
struct slog{
   int sv,poz;
};
vector<slog> sniz;
bool posv(slog a,slog b){
   return a.sv<b.sv;
}
struct cvor{
   int cnt,mlt,rez;
};
vector<cvor> st;
vector<int> fwt;
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){
   if(akt==false){
      st[gde].rez=-1;
   }
   else
      st[gde].rez=0;
   gde/=2;
   while(gde){
      st[gde]=opr(st[gde*2],st[gde*2+1]);
      gde/=2;
   }
}
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;
   K=1;
   while(K<2*M)
      K<<=1;

   on.resize(M+5);
   off.resize(M+5);
   sniz.resize(M+5);
   fwt.resize(M+5);


   stepen[0]=1;
   for(int i=1;i<=M;i++)
      stepen[i]=(stepen[i-1]*(ll)b)%MOD;
   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;
   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++){
      sniz[i].poz=i;
      sniz[i].sv=niz[i];
   }
   sort(sniz.begin()+1,sniz.begin()+1+M,posv);
   for(int i=1;i<=M;i++)
      niz[sniz[i].poz]=i;
   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]);
   }
   fwt.clear();
   fwt.shrink_to_fit();
   int upok=K;
   for(int i=1;i<=M;i++)
      niz[i]=sniz[i].poz;
   sniz.clear();
   sniz.shrink_to_fit();

   st.resize(K+K);
   for(int i=M;i>=1;i--){
      st[upok].cnt=1;
      st[upok].mlt=0;
      st[upok].rez=-1;
      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);
      on[l].push_back(upok);
      off[niz[i]].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;
   }
   st.clear();
   st.shrink_to_fit();

   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

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

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 612 KB Output is correct
2 Correct 1 ms 468 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 4568 KB Output is correct
2 Correct 13 ms 4168 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4532 KB Output is correct
2 Correct 14 ms 4500 KB Output is correct
3 Correct 2 ms 852 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 36852 KB Output is correct
2 Correct 144 ms 38048 KB Output is correct
3 Correct 274 ms 40024 KB Output is correct
4 Correct 294 ms 40124 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 39428 KB Output is correct
2 Correct 279 ms 39748 KB Output is correct
3 Correct 159 ms 38888 KB Output is correct
4 Correct 147 ms 38940 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 38988 KB Output is correct
2 Correct 150 ms 39076 KB Output is correct
3 Correct 198 ms 39120 KB Output is correct

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 119 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 258 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 89 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 94 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -