oj.uz

Submission #382023

# Submission time Handle Problem Language Result Execution time Memory
382023 2021-03-26T09:49:09 Z dorijanlendvaj Intergalactic ship (IZhO19_xorsum) C++14
100 / 100
 175 ms 6508 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 3 ms 876 KB Output is correct
7 Correct 3 ms 876 KB Output is correct
8 Correct 2 ms 876 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1644 KB Output is correct
2 Correct 5 ms 1004 KB Output is correct
3 Correct 2 ms 876 KB Output is correct
4 Correct 2 ms 876 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 5356 KB Output is correct
2 Correct 112 ms 5484 KB Output is correct
3 Correct 116 ms 5356 KB Output is correct
4 Correct 116 ms 5504 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 492 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 3 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 3 ms 492 KB Output is correct
7 Correct 3 ms 492 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 3 ms 876 KB Output is correct
7 Correct 3 ms 876 KB Output is correct
8 Correct 2 ms 876 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 3 ms 876 KB Output is correct
13 Correct 3 ms 876 KB Output is correct
14 Correct 3 ms 876 KB Output is correct
15 Correct 3 ms 876 KB Output is correct

Subtask #8
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 3 ms 876 KB Output is correct
7 Correct 3 ms 876 KB Output is correct
8 Correct 2 ms 876 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 3 ms 492 KB Output is correct
13 Correct 2 ms 492 KB Output is correct
14 Correct 3 ms 492 KB Output is correct
15 Correct 3 ms 492 KB Output is correct
16 Correct 3 ms 876 KB Output is correct
17 Correct 3 ms 876 KB Output is correct
18 Correct 3 ms 876 KB Output is correct
19 Correct 3 ms 876 KB Output is correct
20 Correct 67 ms 3948 KB Output is correct
21 Correct 66 ms 3948 KB Output is correct
22 Correct 59 ms 3820 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 3 ms 876 KB Output is correct
7 Correct 3 ms 876 KB Output is correct
8 Correct 2 ms 876 KB Output is correct
9 Correct 29 ms 1644 KB Output is correct
10 Correct 5 ms 1004 KB Output is correct
11 Correct 2 ms 876 KB Output is correct
12 Correct 2 ms 876 KB Output is correct
13 Correct 110 ms 5356 KB Output is correct
14 Correct 112 ms 5484 KB Output is correct
15 Correct 116 ms 5356 KB Output is correct
16 Correct 116 ms 5504 KB Output is correct
17 Correct 1 ms 492 KB Output is correct
18 Correct 1 ms 620 KB Output is correct
19 Correct 1 ms 492 KB Output is correct
20 Correct 3 ms 492 KB Output is correct
21 Correct 2 ms 492 KB Output is correct
22 Correct 3 ms 492 KB Output is correct
23 Correct 3 ms 492 KB Output is correct
24 Correct 3 ms 876 KB Output is correct
25 Correct 3 ms 876 KB Output is correct
26 Correct 3 ms 876 KB Output is correct
27 Correct 3 ms 876 KB Output is correct
28 Correct 67 ms 3948 KB Output is correct
29 Correct 66 ms 3948 KB Output is correct
30 Correct 59 ms 3820 KB Output is correct
31 Correct 163 ms 6508 KB Output is correct
32 Correct 175 ms 6508 KB Output is correct
33 Correct 155 ms 6380 KB Output is correct
34 Correct 138 ms 6252 KB Output is correct
35 Correct 138 ms 6252 KB Output is correct
36 Correct 135 ms 6396 KB Output is correct