Submission #408985

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
408985	2021-05-20T00:56:38 Z	8e7	Intergalactic ship (IZhO19_xorsum)	C++14	100 / 100	901 ms	12408 KB

xorsum

//Challenge: Accepted
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <stack>
#include <set>
#define ll long long
#define maxn 1005
#define maxq 100005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
#define int ll
using namespace std;
int a[maxn];
struct query{
	int l, r, x;
	query(int a, int b, int c) {
		l = a, r = b, x = c;
	}
	query() {
		l = 0, r = 0, x = 0;
	}
} que[maxq];
ll po[maxq];
int n, q;
ll cnt[maxn][maxn], one[2][maxn];
void build2d(int mask) {
	for (int i = 1;i <= n;i++) {
		for (int j = 1;j <= n;j++) cnt[i][j] = 0;
	}
	for (int i = 0;i < q;i++) {
		if ((que[i].x & mask) == mask) cnt[que[i].l][que[i].r]++;
	}	
	for (int i = 1;i <= n;i++) {
		for (int j = n;j >= i;j--) cnt[i][j] += cnt[i][j + 1];
		for (int j = n;j >= i;j--) cnt[i][j] += cnt[i - 1][j];
	}
}
void build1d(ll arr[], int mask) {
	for (int i = 0;i <= n;i++) arr[i] = 0;
	for (int i = 0;i < q;i++) {
		if ((que[i].x & mask) == mask) {
			arr[que[i].l]++, arr[que[i].r + 1]--;
		}
	}
	for (int i = 1;i <= n;i++) arr[i] += arr[i - 1];
}
ll ans = 0;
void solve(int b1, int b2) {
	build1d(one[0], b1), build1d(one[1], b2);
	build2d(b1 | b2);
	ll num = (ll)b1 * b2, tmp = 0;
	//cout << b1 << " " << b2 << endl;
	for (int i = 1;i <= n;i++) {
		for (int j = i;j <= n;j++) {
			bool bi = a[i] & b1, bj = a[j] & b2;
			int l = one[0][i], r = one[1][j], both = cnt[i][j];
			l -= both, r -= both;
			ll other = po[q - l - r - both];
			ll pl0 = l == 0 ? 1 : po[l - 1], pl1 = l == 0 ? 0 : po[l - 1];
			ll pr0 = r == 0 ? 1 : po[r - 1], pr1 = r == 0 ? 0 : po[r - 1];
			ll both0 = both == 0 ? 1 : po[both - 1], both1 = both == 0 ? 0 : po[both - 1];
			if (bi) swap(pl0, pl1);
			if (bj) swap(pr0, pr1);
			//cout << i << " " << j << " " << both0 * pl1 * pr1 * i * (n - j + 1) * other << " " << both1 * pl0 * pr0 * i * (n - j + 1) * other << endl;
			//cout << other << endl;
			ll val =  (both0 * pl1 % mod * pr1 % mod + both1 * pl0 % mod * pr0 % mod) % mod * i * (n - j +1) % mod * other % mod;	
			tmp = (tmp + val * (i == j ? 1 : 2) )% mod;
		}
	}	
	ans = (ans + num * tmp) % mod;
	
}
signed main() {
	io
	po[0] = 1;
	for (int i = 1;i < maxq;i++) po[i] = po[i - 1] * 2 % mod;
	cin >>n;
	for (int i = 1;i <= n;i++) cin >> a[i];
	cin >> q;
	for (int i = 0;i < q;i++) {
		cin >> que[i].l >> que[i].r >> que[i].x;	
	}	
	for (int i = 0;i < 7;i++) {
		for (int j = 0;j < 7;j++) {
			solve(1<<i, 1<<j);
		}
	}
	cout << ans << endl;
}
/*
2
1 3
1
1 2 2

5
1 2 3 4 5
0

*/

Subtask #1
4.0 / 4.0

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

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	3404 KB	Output is correct
2	Correct	3 ms	3404 KB	Output is correct
3	Correct	3 ms	3404 KB	Output is correct
4	Correct	3 ms	3404 KB	Output is correct
5	Correct	3 ms	3488 KB	Output is correct
6	Correct	12 ms	3948 KB	Output is correct
7	Correct	11 ms	3948 KB	Output is correct
8	Correct	10 ms	3944 KB	Output is correct

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	108 ms	3908 KB	Output is correct
2	Correct	21 ms	3916 KB	Output is correct
3	Correct	12 ms	3964 KB	Output is correct
4	Correct	12 ms	3960 KB	Output is correct

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	733 ms	11324 KB	Output is correct
2	Correct	736 ms	11340 KB	Output is correct
3	Correct	730 ms	11320 KB	Output is correct
4	Correct	728 ms	11340 KB	Output is correct

Subtask #5
8.0 / 8.0

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

Subtask #6
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	3532 KB	Output is correct
2	Correct	3 ms	3532 KB	Output is correct
3	Correct	4 ms	3584 KB	Output is correct
4	Correct	8 ms	3532 KB	Output is correct
5	Correct	8 ms	3532 KB	Output is correct
6	Correct	8 ms	3600 KB	Output is correct
7	Correct	9 ms	3532 KB	Output is correct

Subtask #7
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	3404 KB	Output is correct
2	Correct	3 ms	3404 KB	Output is correct
3	Correct	3 ms	3404 KB	Output is correct
4	Correct	3 ms	3404 KB	Output is correct
5	Correct	3 ms	3488 KB	Output is correct
6	Correct	12 ms	3948 KB	Output is correct
7	Correct	11 ms	3948 KB	Output is correct
8	Correct	10 ms	3944 KB	Output is correct
9	Correct	3 ms	3532 KB	Output is correct
10	Correct	3 ms	3532 KB	Output is correct
11	Correct	4 ms	3584 KB	Output is correct
12	Correct	10 ms	3916 KB	Output is correct
13	Correct	10 ms	3916 KB	Output is correct
14	Correct	11 ms	3840 KB	Output is correct
15	Correct	10 ms	3956 KB	Output is correct

Subtask #8
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	3404 KB	Output is correct
2	Correct	3 ms	3404 KB	Output is correct
3	Correct	3 ms	3404 KB	Output is correct
4	Correct	3 ms	3404 KB	Output is correct
5	Correct	3 ms	3488 KB	Output is correct
6	Correct	12 ms	3948 KB	Output is correct
7	Correct	11 ms	3948 KB	Output is correct
8	Correct	10 ms	3944 KB	Output is correct
9	Correct	3 ms	3532 KB	Output is correct
10	Correct	3 ms	3532 KB	Output is correct
11	Correct	4 ms	3584 KB	Output is correct
12	Correct	8 ms	3532 KB	Output is correct
13	Correct	8 ms	3532 KB	Output is correct
14	Correct	8 ms	3600 KB	Output is correct
15	Correct	9 ms	3532 KB	Output is correct
16	Correct	10 ms	3916 KB	Output is correct
17	Correct	10 ms	3916 KB	Output is correct
18	Correct	11 ms	3840 KB	Output is correct
19	Correct	10 ms	3956 KB	Output is correct
20	Correct	328 ms	8440 KB	Output is correct
21	Correct	308 ms	8428 KB	Output is correct
22	Correct	242 ms	8368 KB	Output is correct

Subtask #9
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	3404 KB	Output is correct
2	Correct	3 ms	3404 KB	Output is correct
3	Correct	3 ms	3404 KB	Output is correct
4	Correct	3 ms	3404 KB	Output is correct
5	Correct	3 ms	3488 KB	Output is correct
6	Correct	12 ms	3948 KB	Output is correct
7	Correct	11 ms	3948 KB	Output is correct
8	Correct	10 ms	3944 KB	Output is correct
9	Correct	108 ms	3908 KB	Output is correct
10	Correct	21 ms	3916 KB	Output is correct
11	Correct	12 ms	3964 KB	Output is correct
12	Correct	12 ms	3960 KB	Output is correct
13	Correct	733 ms	11324 KB	Output is correct
14	Correct	736 ms	11340 KB	Output is correct
15	Correct	730 ms	11320 KB	Output is correct
16	Correct	728 ms	11340 KB	Output is correct
17	Correct	3 ms	3532 KB	Output is correct
18	Correct	3 ms	3532 KB	Output is correct
19	Correct	4 ms	3584 KB	Output is correct
20	Correct	8 ms	3532 KB	Output is correct
21	Correct	8 ms	3532 KB	Output is correct
22	Correct	8 ms	3600 KB	Output is correct
23	Correct	9 ms	3532 KB	Output is correct
24	Correct	10 ms	3916 KB	Output is correct
25	Correct	10 ms	3916 KB	Output is correct
26	Correct	11 ms	3840 KB	Output is correct
27	Correct	10 ms	3956 KB	Output is correct
28	Correct	328 ms	8440 KB	Output is correct
29	Correct	308 ms	8428 KB	Output is correct
30	Correct	242 ms	8368 KB	Output is correct
31	Correct	901 ms	12400 KB	Output is correct
32	Correct	874 ms	12408 KB	Output is correct
33	Correct	799 ms	12312 KB	Output is correct
34	Correct	880 ms	12216 KB	Output is correct
35	Correct	864 ms	12204 KB	Output is correct
36	Correct	864 ms	12184 KB	Output is correct

Submission #408985

Compilation message