Submission #636512

#	Time	Username	Problem	Language	Result	Execution time	Memory
636512		valerikk	Intergalactic ship (IZhO19_xorsum)	C++17	0 / 100	765 ms	196004 KiB

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 = cnt[u][v][i][j];
					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: 0 / 4
• Subtask 2: 0 / 5
• Subtask 3: 0 / 6
• Subtask 4: 0 / 9
• Subtask 5: 0 / 8
• Subtask 6: 0 / 11
• Subtask 7: 0 / 19
• Subtask 8: 0 / 30
• Subtask 9: 0 / 8