Submission #382023

#	Time	Username	Problem	Language	Result	Execution time	Memory
382023		dorijanlendvaj	Intergalactic ship (IZhO19_xorsum)	C++14	100 / 100	175 ms	6508 KiB

xorsum

#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<int,int>
using ll=long long;
using ull=unsigned long long;
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vl vector<ll>
#define all(a) begin(a),end(a)

using namespace std;

const int N=3010,MOD=1e9+7;
const char en='\n';
const ll LLINF=1ll<<60;

int mult(ll a,ll b)
{
	return a*b%MOD;
}

void ad(int&a,int b)
{
	a+=b;
	if (a>=MOD) a-=MOD;
}

int q,n,h[N],cn[N][N],cn2[N][10],cn3[N][10][10];
ull has[N][10];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	const int POL=(MOD+1)/2,CET=mult(POL,POL);
	int an=0;
	mt19937_64 rng(324);
	cin>>n;
	for (int i=0;i<n;++i) cin>>h[i];
	cin>>q;
	for (int z=0;z<q;++z)
	{
		int l,r,a;
		cin>>l>>r>>a;
		--l;
		++cn[l][a];
		--cn[r][a];
		ull re=rng();
		for (int b=0;b<7;++b) if (a&(1<<b))
		{
			++cn2[l][b];
			--cn2[r][b];
			has[l][b]^=re;
			has[r][b]^=re;
			for (int c=b+1;c<7;++c) if (a&(1<<c))
			{
				++cn3[l][b][c];
				--cn3[r][b][c];
			}
		}
	}
	for (int i=1;i<n;++i)
	{
		for (int b=0;b<128;++b) cn[i][b]+=cn[i-1][b];
		for (int b=0;b<7;++b) cn2[i][b]+=cn2[i-1][b],has[i][b]^=has[i-1][b];
		for (int b=0;b<7;++b) for (int c=b+1;c<7;++c) cn3[i][b][c]+=cn3[i-1][b][c];
	}
	for (int b=0;b<7;++b) for (int c=0;c<7;++c)
	{
		int mu=1<<(b+c);
		for (int i=0;i<n;++i) for (int j=i+1;j<n;++j)
		{
			int mu2=2*(i+1)*(n-j);
			if (cn2[i][b] && cn2[j][c] && has[i][b]!=has[j][c]) ad(an,mult(mult(mu,mu2),CET));
			if (cn2[i][b] && cn2[j][c] && has[i][b]==has[j][c] && (((h[i]>>b)&1)==((h[j]>>c)&1))) ad(an,mult(mult(mu,mu2),POL));
			if (cn2[i][b] && !cn2[j][c] && (h[j]&(1<<c))) ad(an,mult(mult(mu,mu2),POL));
			if (!cn2[i][b] && cn2[j][c] && (h[i]&(1<<b))) ad(an,mult(mult(mu,mu2),POL));
			if (!cn2[i][b] && !cn2[j][c] && (h[j]&(1<<c)) && (h[i]&(1<<b))) ad(an,mult(mu,mu2));
		}
	}
	for (int b=0;b<7;++b) for (int i=0;i<n;++i)
	{
		int mu=1<<(b*2);
		int mu2=(i+1)*(n-i);
		if (cn2[i][b]) ad(an,mult(mult(mu,mu2),POL));
		if (!cn2[i][b] && (h[i]&(1<<b))) ad(an,mult(mu,mu2));
	}
	for (int b=0;b<7;++b) for (int c=b+1;c<7;++c) for (int i=0;i<n;++i)
	{
		int cnbc=cn3[i][b][c],cnb=cn2[i][b]-cn3[i][b][c],cnc=cn2[i][c]-cn3[i][b][c];
		int mu=1<<(b+c);
		int mu2=2*(i+1)*(n-i);
		if ((cnb && cnbc) || (cnc && cnbc) || (cnb && cnc)) ad(an,mult(mult(mu,mu2),CET));
		else
		{
			if (cnb && (h[i]&(1<<c))) ad(an,mult(mult(mu,mu2),POL));
			if (cnc && (h[i]&(1<<b))) ad(an,mult(mult(mu,mu2),POL));
			if (cnbc && (((h[i]>>b)&1)==((h[i]>>c)&1))) ad(an,mult(mult(mu,mu2),POL));
			if (!cnb && !cnc && !cnbc && (h[i]&(1<<b)) && (h[i]&(1<<c))) ad(an,mult(mu,mu2));
		}
	}
	for (int i=0;i<q;++i) an=mult(an,2);
	cout<<an<<en;
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 9 / 9
• Subtask 5: 8 / 8
• Subtask 6: 11 / 11
• Subtask 7: 19 / 19
• Subtask 8: 30 / 30
• Subtask 9: 8 / 8