Kod źródłowy zgłoszenia nr 928042

#include <bits/stdc++.h>
using namespace std;struct A{vector<int>a,b,c,d,e,f,g,h,i,j,k,l,m;int n=0,o=0;inline int p(int x,int y){int z=f[x];f[x]=l[z];i[z]=y;j[z]=0;k[z]=l[z]=0;return z;}inline void q(int x,int y){l[y]=f[x];f[x]=y;}inline int r(int x,int y,int z){int u=p(x,z),v=l[y];k[u]=y;l[u]=v;l[y]=u;if(v)k[v]=u;else e[x]=u;return u;}inline int s(int x,int y,int z){int u=p(x,z),v=k[y];l[u]=y;k[u]=v;k[y]=u;if(v)l[v]=u;else d[x]=u;return u;}inline void t(int x,int y){int z=k[y],u=l[y];if(z)l[z]=u;else d[x]=u;if(u)k[u]=z;else e[x]=z;q(x,y);}void u(const vector<int>&x,int y){a=x;o=a.size();b.resize(o);c.resize(o);d.resize(o);e.resize(o);f.resize(o);int z=0,u=1;for(int v=0;v<o;++v){b[v]=z;z+=a[v];}for(int v=0;v<o;++v){c[v]=u;u+=a[v]+1;}g.assign(z,0);h.assign(z,0);i.assign(u,0);j.assign(u,0);k.assign(u,0);l.assign(u,0);for(int v=0;v<o;++v){int w=a[v],p=c[v];d[v]=e[v]=p;i[p]=0;j[p]=w;for(int r=0;r<w;++r)h[b[v]+r]=p;f[v]=p+1;for(int s=p+1;s<p+w;++s)l[s]=s+1;if(w>0)l[p+w]=0;}m.assign(y+2,0);if(o>0)m[0]=o;n=0;}inline void v(int x,int y,int z){int u=b[x]+y,v=h[u],w=g[u],p=i[e[x]];if(z>0){int q=l[v];if(!q||i[q]!=w+1)q=r(x,v,w+1);h[u]=q;g[u]=w+1;++j[q];--j[v];if(j[v]==0)t(x,v);}else{int q=k[v];if(!q||i[q]!=w-1)q=s(x,v,w-1);h[u]=q;g[u]=w-1;++j[q];--j[v];if(j[v]==0)t(x,v);}int aa=i[e[x]];if(aa!=p){--m[p];++m[aa];if(aa>n)n=aa;else if(p==n&&m[n]==0)--n;}}inline void w(int x,int y){for(int z=0;z<o;++z)v(z,x%a[z],y);}inline int x()const{return n;}};struct B{int a=0;vector<int>b,c,d,e;int f=1;explicit B(int g=8){h(g);}void h(int g){int i=1;while(i<max(8,g*4))i<<=1;a=i-1;b.assign(i,0);c.assign(i,0);d.assign(i,0);e.clear();e.reserve(g+1);f=1;}inline void i(){++f;if(f==INT_MAX){fill(d.begin(),d.end(),0);f=1;}e.clear();}inline void j(int g){uint64_t h=(uint64_t)g*11995408973635179863ULL;int i=(int)(h&a);while(d[i]==f&&b[i]!=g)i=(i+1)&a;if(d[i]!=f){d[i]=f;b[i]=g;c[i]=1;e.push_back(i);}else ++c[i];}};int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,q;cin>>n>>q;if(n==1){bool o=false;string y;y.reserve(q*2);for(int i=0;i<q;++i){int a;cin>>a;o=!o;y+=(o?'1':'0');y+='\n';}cout<<y;return 0;}int s=(int)sqrt((long double)n);while(1LL*(s+1)*(s+1)<=n)++s;while(1LL*s*s>n)--s;int t=min(n,min(3000,max(2,2*s-2)));if(t&1)--t;if(t<2)t=2;int h=t/2;int l=(n-1)/h;int k=min(n,t+1000);vector<int>lp(n+1,0),pr;pr.reserve(max(1,n/10));for(int i=2;i<=n;++i){if(lp[i]==0){lp[i]=i;pr.push_back(i);}for(int p:pr){long long v=1LL*p*i;if(v>n||p>lp[i])break;lp[(int)v]=p;}}vector<int>sp;for(int p:pr){if(p<=l)sp.push_back(p);else break;}vector<int>bg(n+1,0);for(int p:pr){if(p<=l)continue;for(int m=p;m<=n;m+=p)bg[m]=p;}vector<int>().swap(lp);vector<int>().swap(pr);A ds;ds.u(sp,q);vector<int>wh(n+1,-1),ac;ac.reserve(min(q,n));int cn=0;bool ao=true;vector<int>bc(k+3,0);int bm=0;B ct(k+2);auto si=[&](int x){ct.i();for(int y:ac){int d=x>y?x-y:y-x,p=bg[d];if(p)ct.j(p);}for(int z:ct.e){int t=ct.c[z];if(t>=2)--bc[t];++bc[t+1];if(t+1>bm)bm=t+1;}};auto se=[&](int x){ct.i();for(int y:ac){if(y==x)continue;int d=x>y?x-y:y-x,p=bg[d];if(p)ct.j(p);}for(int z:ct.e){int t=ct.c[z];--bc[t+1];if(t>=2)++bc[t];}while(bm>0&&bc[bm]==0)--bm;};auto rb=[&](){fill(bc.begin(),bc.end(),0);bm=0;for(int i=0;i<(int)ac.size();++i){int x=ac[i];ct.i();for(int j=0;j<i;++j){int y=ac[j],d=x>y?x-y:y-x,p=bg[d];if(p)ct.j(p);}for(int z:ct.e){int t=ct.c[z];if(t>=2)--bc[t];++bc[t+1];if(t+1>bm)bm=t+1;}}ao=true;};string ou;ou.reserve((size_t)q*8);for(int i=0;i<q;++i){int a;cin>>a;if(wh[a]==-1){ds.w(a,+1);if(ao)si(a);wh[a]=(int)ac.size();ac.push_back(a);++cn;if(ao&&cn>k)ao=false;}else{ds.w(a,-1);if(ao)se(a);int b=wh[a],c=ac.back();ac[b]=c;wh[c]=b;ac.pop_back();wh[a]=-1;--cn;if(!ao&&cn<=t)rb();}int an=cn>0?1:0;an=max(an,ds.x());if(cn<=t&&ao)an=max(an,bm);ou+=to_string(an);ou.push_back('\n');}cout<<ou;return 0;}

1
2

#include <bits/stdc++.h>
using namespace std;struct A{vector<int>a,b,c,d,e,f,g,h,i,j,k,l,m;int n=0,o=0;inline int p(int x,int y){int z=f[x];f[x]=l[z];i[z]=y;j[z]=0;k[z]=l[z]=0;return z;}inline void q(int x,int y){l[y]=f[x];f[x]=y;}inline int r(int x,int y,int z){int u=p(x,z),v=l[y];k[u]=y;l[u]=v;l[y]=u;if(v)k[v]=u;else e[x]=u;return u;}inline int s(int x,int y,int z){int u=p(x,z),v=k[y];l[u]=y;k[u]=v;k[y]=u;if(v)l[v]=u;else d[x]=u;return u;}inline void t(int x,int y){int z=k[y],u=l[y];if(z)l[z]=u;else d[x]=u;if(u)k[u]=z;else e[x]=z;q(x,y);}void u(const vector<int>&x,int y){a=x;o=a.size();b.resize(o);c.resize(o);d.resize(o);e.resize(o);f.resize(o);int z=0,u=1;for(int v=0;v<o;++v){b[v]=z;z+=a[v];}for(int v=0;v<o;++v){c[v]=u;u+=a[v]+1;}g.assign(z,0);h.assign(z,0);i.assign(u,0);j.assign(u,0);k.assign(u,0);l.assign(u,0);for(int v=0;v<o;++v){int w=a[v],p=c[v];d[v]=e[v]=p;i[p]=0;j[p]=w;for(int r=0;r<w;++r)h[b[v]+r]=p;f[v]=p+1;for(int s=p+1;s<p+w;++s)l[s]=s+1;if(w>0)l[p+w]=0;}m.assign(y+2,0);if(o>0)m[0]=o;n=0;}inline void v(int x,int y,int z){int u=b[x]+y,v=h[u],w=g[u],p=i[e[x]];if(z>0){int q=l[v];if(!q||i[q]!=w+1)q=r(x,v,w+1);h[u]=q;g[u]=w+1;++j[q];--j[v];if(j[v]==0)t(x,v);}else{int q=k[v];if(!q||i[q]!=w-1)q=s(x,v,w-1);h[u]=q;g[u]=w-1;++j[q];--j[v];if(j[v]==0)t(x,v);}int aa=i[e[x]];if(aa!=p){--m[p];++m[aa];if(aa>n)n=aa;else if(p==n&&m[n]==0)--n;}}inline void w(int x,int y){for(int z=0;z<o;++z)v(z,x%a[z],y);}inline int x()const{return n;}};struct B{int a=0;vector<int>b,c,d,e;int f=1;explicit B(int g=8){h(g);}void h(int g){int i=1;while(i<max(8,g*4))i<<=1;a=i-1;b.assign(i,0);c.assign(i,0);d.assign(i,0);e.clear();e.reserve(g+1);f=1;}inline void i(){++f;if(f==INT_MAX){fill(d.begin(),d.end(),0);f=1;}e.clear();}inline void j(int g){uint64_t h=(uint64_t)g*11995408973635179863ULL;int i=(int)(h&a);while(d[i]==f&&b[i]!=g)i=(i+1)&a;if(d[i]!=f){d[i]=f;b[i]=g;c[i]=1;e.push_back(i);}else ++c[i];}};int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,q;cin>>n>>q;if(n==1){bool o=false;string y;y.reserve(q*2);for(int i=0;i<q;++i){int a;cin>>a;o=!o;y+=(o?'1':'0');y+='\n';}cout<<y;return 0;}int s=(int)sqrt((long double)n);while(1LL*(s+1)*(s+1)<=n)++s;while(1LL*s*s>n)--s;int t=min(n,min(3000,max(2,2*s-2)));if(t&1)--t;if(t<2)t=2;int h=t/2;int l=(n-1)/h;int k=min(n,t+1000);vector<int>lp(n+1,0),pr;pr.reserve(max(1,n/10));for(int i=2;i<=n;++i){if(lp[i]==0){lp[i]=i;pr.push_back(i);}for(int p:pr){long long v=1LL*p*i;if(v>n||p>lp[i])break;lp[(int)v]=p;}}vector<int>sp;for(int p:pr){if(p<=l)sp.push_back(p);else break;}vector<int>bg(n+1,0);for(int p:pr){if(p<=l)continue;for(int m=p;m<=n;m+=p)bg[m]=p;}vector<int>().swap(lp);vector<int>().swap(pr);A ds;ds.u(sp,q);vector<int>wh(n+1,-1),ac;ac.reserve(min(q,n));int cn=0;bool ao=true;vector<int>bc(k+3,0);int bm=0;B ct(k+2);auto si=[&](int x){ct.i();for(int y:ac){int d=x>y?x-y:y-x,p=bg[d];if(p)ct.j(p);}for(int z:ct.e){int t=ct.c[z];if(t>=2)--bc[t];++bc[t+1];if(t+1>bm)bm=t+1;}};auto se=[&](int x){ct.i();for(int y:ac){if(y==x)continue;int d=x>y?x-y:y-x,p=bg[d];if(p)ct.j(p);}for(int z:ct.e){int t=ct.c[z];--bc[t+1];if(t>=2)++bc[t];}while(bm>0&&bc[bm]==0)--bm;};auto rb=[&](){fill(bc.begin(),bc.end(),0);bm=0;for(int i=0;i<(int)ac.size();++i){int x=ac[i];ct.i();for(int j=0;j<i;++j){int y=ac[j],d=x>y?x-y:y-x,p=bg[d];if(p)ct.j(p);}for(int z:ct.e){int t=ct.c[z];if(t>=2)--bc[t];++bc[t+1];if(t+1>bm)bm=t+1;}}ao=true;};string ou;ou.reserve((size_t)q*8);for(int i=0;i<q;++i){int a;cin>>a;if(wh[a]==-1){ds.w(a,+1);if(ao)si(a);wh[a]=(int)ac.size();ac.push_back(a);++cn;if(ao&&cn>k)ao=false;}else{ds.w(a,-1);if(ao)se(a);int b=wh[a],c=ac.back();ac[b]=c;wh[c]=b;ac.pop_back();wh[a]=-1;--cn;if(!ao&&cn<=t)rb();}int an=cn>0?1:0;an=max(an,ds.x());if(cn<=t&&ao)an=max(an,bm);ou+=to_string(an);ou.push_back('\n');}cout<<ou;return 0;}