oj.uz

Submission #770007

# Submission time Handle Problem Language Result Execution time Memory
770007 2023-06-30T16:25:16 Z rainboy Intergalactic ship (IZhO19_xorsum) C
100 / 100
 930 ms 18600 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 668 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 688 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 668 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 688 KB Output is correct
6 Correct 6 ms 1236 KB Output is correct
7 Correct 5 ms 1236 KB Output is correct
8 Correct 5 ms 1236 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 3240 KB Output is correct
2 Correct 20 ms 1448 KB Output is correct
3 Correct 6 ms 1236 KB Output is correct
4 Correct 5 ms 1200 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 16340 KB Output is correct
2 Correct 443 ms 16368 KB Output is correct
3 Correct 408 ms 16364 KB Output is correct
4 Correct 444 ms 16464 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 1 ms 816 KB Output is correct
3 Correct 1 ms 724 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 1 ms 816 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 6 ms 936 KB Output is correct
5 Correct 7 ms 852 KB Output is correct
6 Correct 6 ms 852 KB Output is correct
7 Correct 6 ms 852 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 668 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 688 KB Output is correct
6 Correct 6 ms 1236 KB Output is correct
7 Correct 5 ms 1236 KB Output is correct
8 Correct 5 ms 1236 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 1 ms 816 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 6 ms 1236 KB Output is correct
13 Correct 6 ms 1236 KB Output is correct
14 Correct 6 ms 1236 KB Output is correct
15 Correct 7 ms 1236 KB Output is correct

Subtask #8
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 668 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 688 KB Output is correct
6 Correct 6 ms 1236 KB Output is correct
7 Correct 5 ms 1236 KB Output is correct
8 Correct 5 ms 1236 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 1 ms 816 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 6 ms 936 KB Output is correct
13 Correct 7 ms 852 KB Output is correct
14 Correct 6 ms 852 KB Output is correct
15 Correct 6 ms 852 KB Output is correct
16 Correct 6 ms 1236 KB Output is correct
17 Correct 6 ms 1236 KB Output is correct
18 Correct 6 ms 1236 KB Output is correct
19 Correct 7 ms 1236 KB Output is correct
20 Correct 284 ms 8812 KB Output is correct
21 Correct 239 ms 8784 KB Output is correct
22 Correct 269 ms 8748 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 668 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 688 KB Output is correct
6 Correct 6 ms 1236 KB Output is correct
7 Correct 5 ms 1236 KB Output is correct
8 Correct 5 ms 1236 KB Output is correct
9 Correct 115 ms 3240 KB Output is correct
10 Correct 20 ms 1448 KB Output is correct
11 Correct 6 ms 1236 KB Output is correct
12 Correct 5 ms 1200 KB Output is correct
13 Correct 422 ms 16340 KB Output is correct
14 Correct 443 ms 16368 KB Output is correct
15 Correct 408 ms 16364 KB Output is correct
16 Correct 444 ms 16464 KB Output is correct
17 Correct 2 ms 724 KB Output is correct
18 Correct 1 ms 816 KB Output is correct
19 Correct 1 ms 724 KB Output is correct
20 Correct 6 ms 936 KB Output is correct
21 Correct 7 ms 852 KB Output is correct
22 Correct 6 ms 852 KB Output is correct
23 Correct 6 ms 852 KB Output is correct
24 Correct 6 ms 1236 KB Output is correct
25 Correct 6 ms 1236 KB Output is correct
26 Correct 6 ms 1236 KB Output is correct
27 Correct 7 ms 1236 KB Output is correct
28 Correct 284 ms 8812 KB Output is correct
29 Correct 239 ms 8784 KB Output is correct
30 Correct 269 ms 8748 KB Output is correct
31 Correct 930 ms 18588 KB Output is correct
32 Correct 648 ms 18600 KB Output is correct
33 Correct 922 ms 18504 KB Output is correct
34 Correct 533 ms 18380 KB Output is correct
35 Correct 562 ms 18400 KB Output is correct
36 Correct 558 ms 18384 KB Output is correct