Submission #1132277

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132277		stdfloat	Intergalactic ship (IZhO19_xorsum)	C++20	47 / 100	2095 ms	1864 KiB

xorsum

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = (int)1e5 + 1, md = (int)1e9 + 7;

vector<int> pw(N, 1);

ll MD(ll x) {
	return (x % md + md) % md;
}

int f(bool x, bool y, int a, int b, int c) {
	if (~a) {
		if (!a) return f(x, y, -1, b, c);
		return MD((ll)pw[a - 1] * MD(f(x, y, -1, b, c) + f(!x, !y, -1, b, c)));
	}
	else if (~b) return MD((ll)(b ? pw[b - 1] : x) * f(true, y, -1, -1, c));
	else return (c ? pw[c - 1] : y);
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	for (int i = 1; i < N; i++)
		pw[i] = MD(pw[i - 1] << 1);

	int n;
	cin >> n;

	vector<int> a(n);
	for (auto &i : a)
		cin >> i;

	int q;
	cin >> q;
	
	int l[q], r[q], X[q];
	for (int i = 0; i < q; i++) {
		cin >> l[i] >> r[i] >> X[i]; l[i]--; r[i]--;
	}

	int ans = 0;
	for (int x = 0; x < 8; x++) {
		for (int y = 0; y < 8; y++) {
			for (int i = 0; i < n; i++) {
				for (int j = i; j < n; j++) {
					int A = 0, B = 0, C = 0;
					for (int k = 0; k < q; k++) {
						bool tr1 = (X[k] >> x) & 1, tr2 = (X[k] >> y) & 1;
						bool ok1 = (l[k] <= i && i <= r[k]), ok2 = (l[k] <= j && j <= r[k]);

						A += (tr1 && tr2 && ok1 && ok2);
						B += (tr1 && ok1 && (!tr2 || !ok2));
						C += (tr2 && ok2 && (!tr1 || !ok1));
					}

					int z = 1 + (i != j);
					int vl = MD((ll)z * pw[x] * pw[y]);
					int pr = MD((ll)(i + 1) * (n - j));
					int cnt = f((a[i] >> x) & 1, (a[j] >> y) & 1, A, B, C);

					ans = MD(ans + MD(MD(MD(vl * pr) * cnt) * pw[q - A - B - C]));
				}
			}
		}
	}

	cout << ans;
}

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