QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#1545#535844#8335. Fast Hash TransformZako oni.A unpassed. (Xiangqian Wang, Hao Luo, Wenhao Chu)liqingyangFailed.2025-02-08 17:16:482025-02-08 17:16:48

Details

Extra Test:

Invalid Input

input:

20000 0 0
64 0 0 1396294391744100773 1 1 11055810369358929143 2 0 6549547857565090477 3 1 10703029946595562777 4 1 4378095677458020740 5 0 17883508040800078767 6 1 2547269231103914181 7 0 6617831089155154295 8 0 9635349956050909473 9 0 18202687668322788343 10 1 1447479822116813487 11 0 1236933853590...

output:


result:

FAIL Integer 0 violates the range [1, 20000] (stdin, line 1)

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#535844#8335. Fast Hash TransformliqingyangAC ✓1069ms49020kbC++172.1kb2024-08-28 15:35:522024-08-28 15:35:52

answer

#include<iostream>
#include<cstring>
using namespace std;
struct Hash
{
	unsigned long long x,h[64];
};
inline unsigned long long operator *
(unsigned long long x,const Hash &h)
{
	unsigned long long ret=h.x;
	for(int i=0;i<64;i++)
	{
		if(__builtin_popcountll(x&h.h[i])&1)
		{
			ret^=1ull<<i;
		}
	}
	return ret;
}
inline Hash operator *
(const Hash &a,const Hash &b)
{
	static Hash ret;
	memset(ret.h,0,sizeof(ret.h)),ret.x=b.x;
	for(int i=0;i<64;i++)
	{
		for(int j=0;j<64;j++)
		{
			if(b.h[i]&(1ull<<j))
			{
				ret.h[i]^=a.h[j];
				ret.x^=((a.x>>j)&1)<<i;
			}
		}
	}
	return ret;
}
Hash a[80000];
inline void update(int p)
{
	a[p]=a[p<<1]*a[(p<<1)|1];
}
inline void change(int l,int r,int x,const Hash &v,int p)
{
	if(l==r)
	{
		a[p]=v;
		return;
	}
	int mid=l+r>>1;
	x<=mid?change(l,mid,x,v,p<<1)
	:change(mid+1,r,x,v,(p<<1)|1);
	update(p);
}
void query(int l,int r,int ll,int rr,unsigned long long &x,int p)
{
	if(r<ll||l>rr)
	{
		return;
	}
	if(ll<=l&&r<=rr)
	{
		x=x*a[p];
		return;
	}
	int mid=l+r>>1;
	query(l,mid,ll,rr,x,p<<1);
	query(mid+1,r,ll,rr,x,(p<<1)|1);
}
inline Hash get()
{
	static Hash ret;
	memset(&ret,0,sizeof(ret));
	int m;
	cin>>m;
	while(m--)
	{
		int s;
		bool op;
		unsigned long long v;
		cin>>s>>op>>v;
		for(int i=0;i<64;i++)
		{
			if(op==((v>>i)&1))
			{
				ret.h[i]^=1ull<<(i+64-s&63);
			}
			else if(!op)
			{
				ret.x^=1ull<<i;
			}
		}
	}
	unsigned long long x;
	cin>>x;
	ret.x^=x;
	return ret;
}
int n,q,c;
Hash A[20010];
void build(int l,int r,int p)
{
	if(l==r)
	{
		a[p]=A[l];
		return;
	}
	int mid=l+r>>1;
	build(l,mid,p<<1);
	build(mid+1,r,(p<<1)|1);
	update(p);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>q>>c;
	for(int i=1;i<=n;i++)
	{
		A[i]=get();
	}
	build(1,n,1);
	while(q--)
	{
		bool op;
		cin>>op;
		if(op)
		{
			int x;
			cin>>x;
			change(1,n,x,get(),1);
		}
		else
		{
			int l,r;
			unsigned long long x;
			cin>>l>>r>>x;
			query(1,n,l,r,x,1);
			cout<<x<<'\n';
		}
	}
	return 0;
}