Submission #354359

#	Time	Username	Problem	Language	Result	Execution time	Memory
354359		cheissmart	Intergalactic ship (IZhO19_xorsum)	C++14	100 / 100	752 ms	194412 KiB

xorsum

#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 1003, K = 7, M = 1e9 + 7;

int one[K][N], both[K][K][N][N], in[N], pw2[100005];

signed main()
{
	IO_OP;

	pw2[0] = 1;
	for(int i = 1; i < 100005; i++)
		pw2[i] = pw2[i - 1] * 2 % M;

	int n, q;
	cin >> n;
	for(int i = 0; i < n; i++) cin >> in[i];
	cin >> q;
	for(int i = 0; i < q; i++) {
		int l, r, x;
		cin >> l >> r >> x;
		l--, r--;
		for(int a = 0; a < K; a++) if(x >> a & 1)
			one[a][l]++, one[a][r + 1]--;
		for(int a = 0; a < K; a++) if(x >> a & 1)
			for(int b = 0; b < K; b++) if(x >> b & 1)
				both[a][b][l][r]++;
	}
	for(int a = 0; a < K; a++)
		for(int i = 1; i < n; i++)
			one[a][i] += one[a][i - 1];
	for(int a = 0; a < K; a++)
		for(int b = 0; b < K; b++)
			for(int len = n; len >= 2; len--)
				for(int i = 0; i + len - 1 < n; i++) {
					int j = i + len - 1, t = both[a][b][i][j];
					both[a][b][i][j - 1] += t;
					both[a][b][i + 1][j] += t;
					both[a][b][i + 1][j - 1] -= t;
				}

	int ans = 0;
	for(int i = 0; i < n; i++) {
		for(int j = i; j < n; j++) {
			int occ = (i + 1) * (n - j);
			if(i != j) occ *= 2;
			for(int a = 0; a < K; a++)
				for(int b = 0; b < K; b++) {
					int mul = occ << (a + b);
					int c11 = both[a][b][i][j], c10 = one[a][i] - c11, c01 = one[b][j] - c11, c00 = q - c11 - c01 - c10;
					int b0 = in[i] >> a & 1, b1 = in[j] >> b & 1;
					int res00 = 0, res11 = 0;
					if(c01 && c10) {
						res00 = res11 = pw2[c01 + c10 - 2];
					} else if(!c01 && !c10) {
						if(b0 == 0 && b1 == 0) res00 = 1;
						else if(b0 == 1 && b1 == 1) res11 = 1;
					} else if(c01) {
						if(((b0 ^ 0) == 0 && (b1 ^ 1) == 0) || ((b0 ^ 0) == 0 && (b1 ^ 0) == 0))
							res00 = pw2[c01 - 1];
						if(((b0 ^ 0) == 1 && (b1 ^ 1) == 1) || ((b0 ^ 0) == 1 && (b1 ^ 0) == 1))
							res11 = pw2[c01 - 1];
					} else if(c10){
						if(((b0 ^ 1) == 0 && (b1 ^ 0) == 0) || ((b0 ^ 0) == 0 && (b1 ^ 0) == 0))
							res00 = pw2[c10 - 1];
						if(((b0 ^ 1) == 1 && (b1 ^ 0) == 1) || ((b0 ^ 0) == 1 && (b1 ^ 0) == 1))
							res11 = pw2[c10 - 1];
					} else throw;
					int res = 0;
					if(c11) res = (ll)(res00 + res11) % M * pw2[c11 - 1] % M; 
					else res = res11;
					res = (ll) res * pw2[c00] % M * mul % M;
					ans = (ans + res) % M;
				}
		}
	}
	cout << ans << endl;

}

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