Submission #770007

#	Time	Username	Problem	Language	Result	Execution time	Memory
770007		rainboy	Intergalactic ship (IZhO19_xorsum)	C11	100 / 100	930 ms	18600 KiB

xorsum

#include <stdio.h>

#define N	1000
#define L	7
#define Q	100000
#define MD	1000000007

int pp2[Q + 1];

void init() {
	int i;

	pp2[0] = 1;
	for (i = 1; i <= Q; i++)
		pp2[i] = (long long) pp2[i - 1] * 2 % MD;
}

int dp[N + 1][N + 1][4], n;

void update(int i1, int i2, int j1, int j2, int b) {
	if (i1 > i2 || j1 > j2)
		return;
	dp[i1][j1][b]++, dp[i1][j2 + 1][b]--;
	dp[i2 + 1][j1][b]--, dp[i2 + 1][j2 + 1][b]++;
}

int main() {
	static int aa[N], ll[Q], rr[Q], xx[Q];
	int q, h, i, j, k, l, b, c0, c1, c2, c3, x, ans;

	init();
	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]);
	scanf("%d", &q);
	for (h = 0; h < q; h++)
		scanf("%d%d%d", &ll[h], &rr[h], &xx[h]), ll[h]--, rr[h]--;
	ans = 0;
	for (k = 0; k < L; k++)
		for (l = 0; l < L; l++) {
			for (i = 0; i <= n; i++)
				for (j = 0; j <= n; j++)
					for (b = 0; b < 4; b++)
						dp[i][j][b] = 0;
			for (h = 0; h < q; h++) {
				update(0, ll[h] - 1, 0, ll[h] - 1, 0 << 1 | 0);
				update(0, ll[h] - 1, ll[h], rr[h], 0 << 1 | (xx[h] >> l & 1));
				update(0, ll[h] - 1, rr[h] + 1, n - 1, 0 << 1 | 0);
				update(ll[h], rr[h], ll[h], rr[h], (xx[h] >> k & 1) << 1 | (xx[h] >> l & 1));
				update(ll[h], rr[h], rr[h] + 1, n - 1, (xx[h] >> k & 1) << 1 | 0);
				update(rr[h] + 1, n - 1, rr[h] + 1, n - 1, 0 << 1 | 0);
			}
			for (i = 0; i < n; i++)
				for (j = 1; j < n; j++)
					for (b = 0; b < 4; b++)
						dp[i][j][b] += dp[i][j - 1][b];
			for (i = 1; i < n; i++)
				for (j = 0; j < n; j++)
					for (b = 0; b < 4; b++)
						dp[i][j][b] += dp[i - 1][j][b];
			for (i = 0; i < n; i++)
				for (j = i; j < n; j++) {
					b = ((aa[i] >> k & 1) << 1 | (aa[j] >> l & 1)) ^ 3;
					c0 = dp[i][j][0], c1 = dp[i][j][1], c2 = dp[i][j][2], c3 = dp[i][j][3];
					if (c1 + c2 + c3 == 0) {
						if (b != 0)
							continue;
						x = pp2[c0];
					} else if (c2 + c3 == 0) {
						if (b == 2 || b == 3)
							continue;
						x = pp2[c0 + c1 - 1];
					} else if (c3 + c1 == 0) {
						if (b == 3 || b == 1)
							continue;
						x = pp2[c0 + c2 - 1];
					} else if (c1 + c2 == 0) {
						if (b == 1 || b == 2)
							continue;
						x = pp2[c0 + c3 - 1];
					} else
						x = pp2[c0 + c1 + c2 + c3 - 2];
					ans = (ans + (long long) (1 << k + l) * (i + 1) % MD * (n - j) % MD * (i == j ? 1 : 2) % MD * x) % MD;
				}
		}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

xorsum.c: In function 'main':
xorsum.c:83:39: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   83 |      ans = (ans + (long long) (1 << k + l) * (i + 1) % MD * (n - j) % MD * (i == j ? 1 : 2) % MD * x) % MD;
      |                                     ~~^~~
xorsum.c:32:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
xorsum.c:34:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
xorsum.c:35:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
xorsum.c:37:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |   scanf("%d%d%d", &ll[h], &rr[h], &xx[h]), ll[h]--, rr[h]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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