Submission #636514

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
636514	2022-08-29T12:33:57 Z	valerikk	Intergalactic ship (IZhO19_xorsum)	C++17	100 / 100	1091 ms	196376 KB

xorsum

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define all(a) begin(a), end(a)
#define sz(a) ((int) (a).size())

using ll = long long;
using ld = long double;

const int N = 1005;
const int K = 7;
const int Q = 1e5 + 5;
const int MOD = 1e9 + 7;
const int INV2 = (MOD + 1) / 2;

int add(int a, int b) {
	return a + b < MOD ? a + b : a + b - MOD;
}

int sub(int a, int b) {
	return a - b >= 0 ? a - b : a - b + MOD;
}

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

int n;
int a[N];
int q;
int l[Q], r[Q], x[Q];
int cnt[K][K][N][N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	cin >> q;
	for (int i = 0; i < q; ++i) {
		cin >> l[i] >> r[i] >> x[i];
		--l[i];
		--r[i];
	}
	memset(cnt, 0, sizeof cnt);
	for (int u = 0; u < K; ++u) {
		for (int v = 0; v < K; ++v) {
			for (int i = 0; i < q; ++i) {
				if (((x[i] >> u) & 1) && ((x[i] >> v) & 1)) {
					++cnt[u][v][l[i]][r[i]];
				}
			}
			for (int i = 0; i < n; ++i) {
				for (int j = n - 1; j >= 0; --j) {
					if (i > 0) cnt[u][v][i][j] += cnt[u][v][i - 1][j];
					if (j < n - 1) cnt[u][v][i][j] += cnt[u][v][i][j + 1];
					if (i > 0 && j < n - 1) cnt[u][v][i][j] -= cnt[u][v][i - 1][j + 1];
				}
			}
		}
	}
	int ans = 0;
	for (int u = 0; u < K; ++u) {
		for (int v = 0; v < K; ++v) {
			for (int i = 0; i < n; ++i) {
				for (int j = 0; j < n; ++j) {
					int cnt_i = cnt[u][u][i][i];
					int cnt_j = cnt[v][v][j][j];
					int cnt_both = i <= j ? cnt[u][v][i][j] : cnt[v][u][j][i];
					cnt_i -= cnt_both;
					cnt_j -= cnt_both;
					int need_i = !((a[i] >> u) & 1);
					int need_j = !((a[j] >> v) & 1);
					int cur = mul(min(i, j) + 1, n - max(i, j));
					if (cnt_i) cur = mul(cur, INV2);
					if (cnt_j) cur = mul(cur, INV2);
					if (cnt_both) cur = mul(cur, INV2);
					cur = mul(cur, 1 << (u + v));
					for (int par_both = 0; par_both < 2; ++par_both) {
						if (par_both > cnt_both) continue;
						int par_i = need_i ^ par_both;
						int par_j = need_j ^ par_both;
						if (par_i > cnt_i || par_j > cnt_j) continue;
						ans = add(ans, cur);
					}
				}
			}
		}
	}
	for (int i = 0; i < q; ++i) {
		ans = mul(ans, 2);
	}
	cout << ans << endl;
	return 0;
}

Subtask #1
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	68 ms	193976 KB	Output is correct
2	Correct	73 ms	194004 KB	Output is correct
3	Correct	71 ms	193988 KB	Output is correct
4	Correct	70 ms	193936 KB	Output is correct
5	Correct	77 ms	193996 KB	Output is correct

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	68 ms	193976 KB	Output is correct
2	Correct	73 ms	194004 KB	Output is correct
3	Correct	71 ms	193988 KB	Output is correct
4	Correct	70 ms	193936 KB	Output is correct
5	Correct	77 ms	193996 KB	Output is correct
6	Correct	78 ms	194116 KB	Output is correct
7	Correct	79 ms	193980 KB	Output is correct
8	Correct	76 ms	193996 KB	Output is correct

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	106 ms	195160 KB	Output is correct
2	Correct	98 ms	194224 KB	Output is correct
3	Correct	79 ms	193996 KB	Output is correct
4	Correct	80 ms	194016 KB	Output is correct

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	814 ms	194032 KB	Output is correct
2	Correct	742 ms	194036 KB	Output is correct
3	Correct	720 ms	194036 KB	Output is correct
4	Correct	751 ms	194028 KB	Output is correct

Subtask #5
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	71 ms	193996 KB	Output is correct
2	Correct	71 ms	193940 KB	Output is correct
3	Correct	70 ms	193932 KB	Output is correct

Subtask #6
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	71 ms	193996 KB	Output is correct
2	Correct	71 ms	193940 KB	Output is correct
3	Correct	70 ms	193932 KB	Output is correct
4	Correct	81 ms	194112 KB	Output is correct
5	Correct	71 ms	194060 KB	Output is correct
6	Correct	71 ms	194036 KB	Output is correct
7	Correct	72 ms	194032 KB	Output is correct

Subtask #7
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	68 ms	193976 KB	Output is correct
2	Correct	73 ms	194004 KB	Output is correct
3	Correct	71 ms	193988 KB	Output is correct
4	Correct	70 ms	193936 KB	Output is correct
5	Correct	77 ms	193996 KB	Output is correct
6	Correct	78 ms	194116 KB	Output is correct
7	Correct	79 ms	193980 KB	Output is correct
8	Correct	76 ms	193996 KB	Output is correct
9	Correct	71 ms	193996 KB	Output is correct
10	Correct	71 ms	193940 KB	Output is correct
11	Correct	70 ms	193932 KB	Output is correct
12	Correct	83 ms	193980 KB	Output is correct
13	Correct	82 ms	193940 KB	Output is correct
14	Correct	97 ms	194124 KB	Output is correct
15	Correct	78 ms	193992 KB	Output is correct

Subtask #8
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	68 ms	193976 KB	Output is correct
2	Correct	73 ms	194004 KB	Output is correct
3	Correct	71 ms	193988 KB	Output is correct
4	Correct	70 ms	193936 KB	Output is correct
5	Correct	77 ms	193996 KB	Output is correct
6	Correct	78 ms	194116 KB	Output is correct
7	Correct	79 ms	193980 KB	Output is correct
8	Correct	76 ms	193996 KB	Output is correct
9	Correct	71 ms	193996 KB	Output is correct
10	Correct	71 ms	193940 KB	Output is correct
11	Correct	70 ms	193932 KB	Output is correct
12	Correct	81 ms	194112 KB	Output is correct
13	Correct	71 ms	194060 KB	Output is correct
14	Correct	71 ms	194036 KB	Output is correct
15	Correct	72 ms	194032 KB	Output is correct
16	Correct	83 ms	193980 KB	Output is correct
17	Correct	82 ms	193940 KB	Output is correct
18	Correct	97 ms	194124 KB	Output is correct
19	Correct	78 ms	193992 KB	Output is correct
20	Correct	348 ms	196240 KB	Output is correct
21	Correct	324 ms	196300 KB	Output is correct
22	Correct	321 ms	196176 KB	Output is correct

Subtask #9
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	68 ms	193976 KB	Output is correct
2	Correct	73 ms	194004 KB	Output is correct
3	Correct	71 ms	193988 KB	Output is correct
4	Correct	70 ms	193936 KB	Output is correct
5	Correct	77 ms	193996 KB	Output is correct
6	Correct	78 ms	194116 KB	Output is correct
7	Correct	79 ms	193980 KB	Output is correct
8	Correct	76 ms	193996 KB	Output is correct
9	Correct	106 ms	195160 KB	Output is correct
10	Correct	98 ms	194224 KB	Output is correct
11	Correct	79 ms	193996 KB	Output is correct
12	Correct	80 ms	194016 KB	Output is correct
13	Correct	814 ms	194032 KB	Output is correct
14	Correct	742 ms	194036 KB	Output is correct
15	Correct	720 ms	194036 KB	Output is correct
16	Correct	751 ms	194028 KB	Output is correct
17	Correct	71 ms	193996 KB	Output is correct
18	Correct	71 ms	193940 KB	Output is correct
19	Correct	70 ms	193932 KB	Output is correct
20	Correct	81 ms	194112 KB	Output is correct
21	Correct	71 ms	194060 KB	Output is correct
22	Correct	71 ms	194036 KB	Output is correct
23	Correct	72 ms	194032 KB	Output is correct
24	Correct	83 ms	193980 KB	Output is correct
25	Correct	82 ms	193940 KB	Output is correct
26	Correct	97 ms	194124 KB	Output is correct
27	Correct	78 ms	193992 KB	Output is correct
28	Correct	348 ms	196240 KB	Output is correct
29	Correct	324 ms	196300 KB	Output is correct
30	Correct	321 ms	196176 KB	Output is correct
31	Correct	1091 ms	196376 KB	Output is correct
32	Correct	906 ms	196260 KB	Output is correct
33	Correct	1066 ms	196164 KB	Output is correct
34	Correct	943 ms	196072 KB	Output is correct
35	Correct	948 ms	196172 KB	Output is correct
36	Correct	949 ms	196028 KB	Output is correct

Submission #636514

Compilation message