제출 #854783

#제출 시각아이디문제언어결과실행 시간메모리
854783amirhoseinfar1385Matching (CEOI11_mat)C++17
0 / 100
201 ms49604 KiB
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") unsigned int n,m; const unsigned int maxn=1000000+10; unsigned int all[maxn],allb[maxn],hashn=0,base2=3427793,hashn2=0,mod2=987432683,mod=1e9+7,base=3427903,mp[maxn],smp[maxn]; char c; void fastscan(unsigned int &nu) { nu = 0; c = getchar(); for (; (c>47 && c<58); c=getchar()) nu = nu *10 + c - 48; } /*inline unsigned int ww2(unsigned int a){ if(a>=mod2){ a-=mod2; } return a; }*/ inline unsigned int ww(unsigned int a){ if(a>=mod) { a-=mod; } return a; } inline void aval(){ mp[0]=1; smp[0]=0; smp[1]=1; for(unsigned int i=1;i<maxn-1;i++){ mp[i]=1ll*mp[i-1]*base%mod; smp[i+1]=ww(smp[i]+mp[i]); } // mp2[0]=1; // smp2[0]=0; // smp2[1]=1; // for(unsigned int i=1;i<maxn-1;i++){ // mp2[i]=1ll*mp2[i-1]*base2%mod2; // smp2[i+1]=ww2(smp2[i]+mp2[i]); // } } unsigned int kaf=(1<<20); struct segment{ struct node{ unsigned int len,hash,lazy; //unsigned int hash2; node(){ len=hash=lazy=0; //hash2=0; } }; node seg[(1<<21)]; inline node merge(node a,node b){ if(a.lazy!=0){ if(a.len==0){ //hehe; } else if(a.len==1){ a.hash+=mod-a.lazy; a.hash=ww(a.hash); } else{ a.hash+=mod-(1ll*smp[a.len]*a.lazy%mod); a.hash=ww(a.hash); } // a.hash2+=mod2-(1ll*smp2[a.len]*a.lazy%mod2); // a.hash2=ww2(a.hash2); a.lazy=0; } if(b.len==0){ return a; } if(b.lazy!=0){ if(b.len==1){ b.hash+=mod-b.lazy; b.hash=ww(b.hash); } else{ b.hash+=mod-(1ll*smp[b.len]*b.lazy%mod); b.hash=ww(b.hash); } // b.hash2+=mod2-(1ll*smp2[b.len]*b.lazy%mod2); // b.hash2=ww2(b.hash2); b.lazy=0; } if(a.len==0){ return b; } a.hash=1ll*a.hash*mp[b.len]%mod; a.hash+=b.hash; a.hash=ww(a.hash); //a.hash2=1ll*a.hash2*mp2[b.len]%mod2; //a.hash2+=b.hash2; //a.hash2=ww2(a.hash2); a.len+=b.len; return a; } inline void calc(unsigned int i){ if(i>=kaf){ if(seg[i].lazy==0){ return ; } if(seg[i].len==0){ seg[i].lazy=seg[i].hash=0; //seg[i].hash2=0; return ; } seg[i].hash+=mod-seg[i].lazy; seg[i].hash=ww(seg[i].hash); // seg[i].hash2+=mod2-seg[i].lazy; // seg[i].hash2=ww2(seg[i].hash2); return ; } seg[i]=merge(seg[(i<<1)],seg[(i<<1)^1]); } inline void shift(unsigned int i){ if(i>=kaf){ return calc(i); } if(seg[i].lazy==0) { return ; } seg[(i<<1)].lazy+=seg[i].lazy; seg[(i<<1)^1].lazy+=seg[i].lazy; seg[i].lazy=0; return ; } void ins(unsigned int i,unsigned int l,unsigned int r,unsigned int tl,unsigned int w){ if(l>r||l>tl||r<tl){ return ; } if(l>=tl&&r<=tl){ if(w==0){ seg[i].len=0; seg[i].hash=0; // seg[i].hash2=0; seg[i].lazy=0; } else{ seg[i].len=1; seg[i].hash=w; // seg[i].hash2=w; seg[i].lazy=0; } //cout<<l<<" ins "<<r<<" "<<w<<" "<<seg[i].hash<<"\n"; return ; } shift(i); unsigned int m=(l+r)>>1; if(tl<=m){ ins((i<<1),l,m,tl,w); } else{ ins((i<<1)^1,m+1,r,tl,w); } calc(i); } void upd(unsigned int i,unsigned int l,unsigned int r,unsigned int tl,unsigned int tr){ if(l>r||l>tr||r<tl||tl>tr){ return ; } if(l>=tl&&r<=tr){ // calc(i); seg[i].lazy++; return ; } shift(i); unsigned int m=(l+r)>>1; upd((i<<1),l,m,tl,tr); upd((i<<1)^1,m+1,r,tl,tr); calc(i); } unsigned int pors(){ //if(seg[1].hash==hashn&&seg[1].hash2==hashn2){ if(seg[1].hash==hashn){ return 1; } return 0; } }seg; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); aval(); fastscan(n); fastscan(m); unsigned int fn=n-1; for(unsigned int i=0;i<n;i++){ fastscan(all[i]); //cin>>all[i]; //hashn2+=1ll*mp2[fn]*all[i]%mod2; hashn+=1ll*mp[fn]*all[i]%mod; //hashn2=ww2(hashn2); hashn=ww(hashn); fn--; } for(unsigned int i=0;i<m;i++){ fastscan(allb[i]); //cin>>allb[i]; } unsigned int res=0; for(unsigned int i=0;i<m;i++){ //cout<<i<<" "<<seg.seg[1].hash<<"\n"; if(i>=n){ unsigned int p=allb[i-n]; seg.ins(1,0,kaf-1,p,0); // seg.upd(1,0,kaf-1,0,m+1); seg.seg[1].lazy++; } unsigned int p=allb[i]; seg.ins(1,0,kaf-1,p,min(n,i+1)); if(i>=n-1){ if(seg.pors()){ res++; } } } cout<<res<<"\n"; }
#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...