제출 #836785

#제출 시각아이디문제언어결과실행 시간메모리
836785NemanjaSo2005Matching (CEOI11_mat)C++17
36 / 100
233 ms65536 KiB
#include<bits/stdc++.h> #define ll long long using namespace std; int N,K,M,patern[1000005],niz[1000005],oduz[1000005],kol[1000005],H,H2; int MOD=1000000009,b=1000003,stepen[1000005]; vector<int> on[1000005],off[1000005],R; struct slog{ int sv,poz; } sniz[1000005]; bool posv(slog a,slog b){ return a.sv<b.sv; } struct cvor{ int cnt,mlt,rez; bool on; }st[4200000]; cvor opr(cvor a,cvor b){ if(a.on==false) return b; if(b.on==false) 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){ st[gde].on=akt; gde/=2; while(gde){ st[gde]=opr(st[gde*2],st[gde*2+1]); gde/=2; } } int fwt[1000005]; 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; stepen[0]=1; for(int i=1;i<=M;i++) stepen[i]=(stepen[i-1]*(ll)b)%MOD; K=1; while(K<2*M) K<<=1; 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; /*cout<<"MENI JE"<<endl; for(int i=1;i<=N;i++) cout<<niz[i]<<" "; cout<<endl;*/ for(int i=1;i<=N;i++){ fadd(niz[i],1); //cout<<i-fsum(niz[i])<<" "; H=(H+((ll)i-fsum(niz[i]))*stepen[i])%MOD; } //cout<<endl; 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+1,sniz+1+M,posv); for(int i=1;i<=M;i++) niz[sniz[i].poz]=i; int upok=K; for(int i=M;i>=1;i--){ st[upok].cnt=1; st[upok].mlt=0; st[upok].rez=0; on[sniz[i].poz].push_back(upok); upok++; st[upok].cnt=0; st[upok].mlt=stepen[sniz[i].poz]; st[upok].rez=0; st[upok].on=false; int l=max(1,sniz[i].poz-N); on[l].push_back(upok); off[sniz[i].poz].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; // cout<<oduz[i]<<" "; } // cout<<endl; 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]); //cout<<kol[i]<<" "; } // cout<<endl; for(int i=1;i<=N;i++) H2=(H2+(ll)kol[i]*stepen[i])%MOD; //cout<<H<<" "<<H2<<endl; 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; // cout<<i<<" "<<H<<" "<<H2<<endl; 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; } /* 5 10 2 1 5 3 4 5 6 3 8 12 7 1 10 11 9 */

컴파일 시 표준 에러 (stderr) 메시지

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